題意：
求最小的離散對數(shù)B 使得A^B == C (mod P) P是質(zhì)數(shù) 或者判無解
做法：
數(shù)論題..對于比我大的同學(xué)肯定覺得很簡單。。
由歐拉定理 A^phi(P) == 1 (mod P) (phi(prime)=prime-1)
得到 A^(B+phi(P)) == c (mod P) A^(B-Phi(P)) ==c (mod P)
所以可以肯定的一點(diǎn)是 如果 [0,phi(P))內(nèi)無解 由此式子的周期性必然不會有更多解
一個樸素的想法：枚舉 B∈[0,phi(P)) 檢驗(yàn) A^B是否 == C(mod P)
問題又出現(xiàn)了 P是個質(zhì)數(shù) phi(P)=P-1 必然TLE
所以就必須用空間換時間。
設(shè)得到的答案是B B=X*sqrt(P)+Y 注意到X,Y<=sqrt(P)
列式并化簡：
A^(X*sqrt(P)+Y) == C (mod P)
(A*sqrt(P))^X*A^Y == C (mod P)
設(shè) T=A*sqrt(P) 原式即 T^X*A^Y == C (mod P)
兩邊同除以 A^Y 得到 T^X == C/(A^Y) (mod P)
好吧 到現(xiàn)在 做法就已經(jīng)浮出水面了
我們預(yù)處理T^i (mod P) 最多sqrt(P)個 (i<X)
手寫hash或者用map直接存下來二元組 (T^X (mod P),X)
然后枚舉 Y∈[0,sqrt(P)) 最多sqrt(P)個
對于每個Y 我們求出 C/(A^Y) (mod P) 然后在hash或者map中查找這個值
如果 (C/(A^Y) (mod P),X) 存在 那么說明 X*sqrt(P)+Y 是可以作為答案的
最后答案便是所有滿足條件的 X*sqrt(P)+Y 中的最小值。
如果你不知道 C/(A^Y) (mod P) 怎么求
那就繼續(xù)看下去吧
C/(A^Y) (mod P) == C*((1/A^Y) mod P)
(1/A^Y) (mod P) == (A^Y)^-1 (mod P)
即 (A^Y)^(phi(P)-1) (mod P)
所以 C/(A^Y) (mod P) 就等于C*(A^Y)^(phi(P)-1) (mod P)
這樣就解決了此題。
1 #include <cstdio>
2 #include <cstring>
3 #include <cmath>
4 #define Prime 899037
5 #define oo 2000000005
6 #define min(a,b) ((a)<(b)?(a):(b))
7 int P,B,N;
8 int H[Prime],V[Prime];
9 inline int pow(int u,int v)
10 {
11 int ret=1;
12 for (int tmp=u;v;v>>=1,tmp=(tmp*(long long)tmp)%P)
13 if (v&1) ret=(ret*(long long)tmp)%P;
14 return ret;
15 }
16 inline void Hpush(int u,int v)
17 {
18 int t=u%Prime;
19 for (;H[t];)
20 {
21 if (H[t]==u) return;
22 if (++t==P) t-=P;
23 }
24 H[t]=u,V[t]=v;
25 }
26 inline int Hpop(int u)
27 {
28 int t=u%Prime;
29 for (;H[t];)
30 {
31 if (H[t]==u) return V[t];
32 if (++t==P) t-=P;
33 }
34 return oo;
35 }
36 int main()
37 {
38 for (;scanf("%d%d%d",&P,&B,&N)!=EOF;)
39 {
40 int ret=oo+1;
41 memset(H,0,sizeof(H));
42 memset(V,-1,sizeof(V));
43 int sqrtP=(int)sqrt((double)P),Bsp=pow(B,sqrtP);
44 for (int i=0,val=1;i<=sqrtP;++i,val=(val*(long long)Bsp)%P)
45 Hpush(val,i);
46 for (int i=0,val=1;i<=sqrtP;++i,val=(val*(long long)B)%P)
47 {
48 int h=(N*(long long)pow(val,P-2))%P,v=Hpop(h);
49 if (v<oo&&v*sqrtP+i<ret) ret=v*sqrtP+i;
50 }
51 if (ret>oo) puts("no solution");
52 else printf("%d\n",ret);
53 }
54 return 0;
55 }
56