POJ 2417 Discrete Logging

 1 #include<algorithm>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<cstring>
 5 #include<iostream>
 6 #include<map>
 7 #define ll long long
 8 ll p;
 9 std::map<ll , int> mp;
10 ll Pow(ll x,ll y){
11     ll res=1;
12     while (y){
13         if (y%2) res=(res*x)%p;
14         x=(x*x)%p;
15         y/=2;
16     }
17     return res;
18 }
19 ll solve(ll a,ll b){
20     a%=p;
21     if (a==0){
22         if (b==0) return 0;
23         else return -1;
24     }
25     mp.clear();
26     ll m=sqrt(p)+1,t=1,I=1;
27     for (int i=1;i<m;i++){
28         t=t*a%p;
29         if (!mp[t]) mp[t]=i;
30     }
31     mp[1]=m+1;
32     ll Im=Pow(a,p-1-m);
33     for (int k=0;k<m;k++){
34         int i=mp[I*b%p];
35         if (i!=0){
36             if (i==m+1) i=0;
37             return i+k*m;
38         }
39         I=I*Im%p;
40     }
41     return -1;
42 }
43 int main(){
44     ll a,b;
45     while (scanf("%lld%lld%lld",&p,&a,&b)!=EOF){
46         ll ans=solve(a,b);
47         if (ans==-1) puts("no solution");
48         else printf("%lld\n",ans);
49     }
50 }