题意：
求最小的离散对数B 使得A^B == C (mod P) P是质数 或者判无解
做法：
数论题..对于比我大的同学肯定觉得很简单。。
由欧拉定理 A^phi(P) == 1 (mod P) (phi(prime)=prime-1)
得到 A^(B+phi(P)) == c (mod P) A^(B-Phi(P)) ==c (mod P)
所以可以肯定的一点是 如果 [0,phi(P))内无解 由此式子的周期性必然不会有更多解
一个朴素的想法：枚举 B∈[0,phi(P)) 检验 A^B是否 == C(mod P)
问题又出现了 P是个质数 phi(P)=P-1 必然TLE
所以就必须用空间换时间。
设得到的答案是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)
设 T=A*sqrt(P) 原式即 T^X*A^Y == C (mod P)
两边同除以 A^Y 得到 T^X == C/(A^Y) (mod P)
好吧 到现在 做法就已经浮出水面了
我们预处理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) 怎么求
那就继续看下去吧
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