Abstract

HDU 4335 What is N?

數(shù)論

?

Body

Source

http://acm.hdu.edu.cn/showproblem.php?pid=4335

Description

給定p, b(0<=b<p<=10^5)和m(1<=m<2^64)，問有多少個n滿足n^(n!)=b (mod p)。

Solution

首先要知道這個結論：（反正比賽時我是不知道，只好orz福大核武景潤后人了）

a^x = a^(x mod phi(c)+phi(c)) (mod c), x>=phi(c)

然后就很簡單了。把[0,m]分成三部分：

1. 對于n!<phi(p)的就枚舉；

2. phi(p)<=n!<t!, t=min{x|x! mod phi(p)=0}

套公式就是

n^(n! mod phi(p)+phi(p))=b (mod p)

同樣也是枚舉，弄個變量存n! mod phi(p)就行。

3. n>=t, t=min{x|x! mod phi(p)=0}

這時候公式就變?yōu)?/p>

n^phi(p)=b (mod p)

也就是

(n mod p)^phi(p)=b (mod p)

于是n mod p就循環(huán)了……

Code

#include <iostream> #include <cassert> #include <cstdio> #include <cstring> #include <algorithm> using namespace std;typedef unsigned long long LL;const int MAX = 200020; int p[MAX], pcnt=0; int minf[MAX]; int phi[MAX]; void initprime() {for (int i = 2; i < MAX; ++i) {if (!minf[i]) {p[pcnt++] = i;phi[i] = i-1;}for (int j = 0; j < pcnt && p[j]*i < MAX; ++j) {minf[p[j]*i] = p[j];if (i%p[j])phi[p[j]*i] = phi[i]*(p[j]-1);else {phi[p[j]*i] = phi[i]*p[j];break;}}} }LL mod;LL pow(LL x, LL p) {LL res = 1;for (; p; p>>=1) {if (p&1) res = (res*x)%mod;x = (x*x)%mod;}return res; }int T; int b, c; LL a; LL ring[MAX], ringcnt;int main() {initprime();cin>>T;LL i, j, k, n;LL php;for (int t = 1; t <= T; ++t) {cin>>b>>c>>a;mod = c;printf("Case #%d: ", t);if (c==1) {if (b==0) {if (a==18446744073709551615ULL)cout<<"18446744073709551616"<<endl;elsecout<<a+1<<endl;}else cout<<0<<endl;continue;}LL ans = 0;LL fac = 1;php = phi[c];for (n = 0; n<=a && fac<php; ++n) {if (pow(n, fac)==b) ++ans;fac *= (n+1);}fac %= php;for (; n<=a && fac; ++n) {if (pow(n, fac+php)==b) ++ans;fac = fac*(n+1)%php;}if (n<=a) {ringcnt = 0;for (i = 0; i < c; ++i) {ring[i] = pow(n+i, php);if (ring[i]==b) ++ringcnt;}LL group = (a-n+1)/c;ans += group*ringcnt;LL left = (a-n+1)-group*c;for (i = 0; i < left; ++i)ans += (ring[i]==b);}cout<<ans<<endl;}return 0; }

轉載于:https://www.cnblogs.com/jffifa/archive/2012/08/03/2622247.html

總結

以上是生活随笔為你收集整理的[代码]HDU 4335 What is N?的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。