【BZOJ】【3239】Discrete Logging

江南才子

BSGSBSGS裸题，嗯题目中也有提示：求a^m (mod p)的逆元可用快速幂，即 pow(a,P-m-1,P) * (a^m) = 1 (mod p)

1 /**************************************************************
 2   Problem: 3239
 3   User: Tunix
 4   Language: C++
 5   Result: Accepted
 6   Time:208 ms
 7   Memory:2872 kb
 8 ****************************************************************/
 9  
10 //BZOJ 3239
11 #include<cmath>
12 #include<map>
13 #include<cstdio>
14 #include<cstring>
15 #include<cstdlib>
16 #include<iostream>
17 #include<algorithm>
18 #define rep(i,n) for(int i=0;i<n;++i)
19 #define F(i,j,n) for(int i=j;i<=n;++i)
20 #define D(i,j,n) for(int i=j;i>=n;--i)
21 using namespace std;
22 int getint(){
23   int v=0,sign=1; char ch=getchar();
24   while(!isdigit(ch)) {if(ch=='-') sign=-1; ch=getchar();}
25   while(isdigit(ch))  {v=v*10+ch-'0'; ch=getchar();}
26   return v*sign;
27 }
28 /*******************template********************/
29 typedef long long LL;
30 LL pow(LL a,LL b,LL P){
31   LL r=1,base=a%P;
32   while(b){
33     if (b&1) r=r*base%P;
34     base=base*base%P;
35     b>>=1;
36   }
37   return r;
38 }
39 LL log_mod(LL a,LL b,LL P){
40   LL m,v,e=1;
41   m=ceil(sqrt(P+0.5));
42   v=pow(a,P-m-1,P);
43   map<LL,LL>x;
44   x[1]=0;
45   for(int i=1;i<m;++i){
46     e=e*a%P;
47     if(!x.count(e)) x[e]=i;
48   }
49   rep(i,m){
50     if (x.count(b)) return (LL) i*m+x[b];
51     b=b*v%P;
52   }
53   return -1;
54 }
55 int main(){
56   LL P,b,n;
57   while(scanf("%lld%lld%lld",&P,&b,&n)!=EOF){
58     b%=P; n%=P;
59     if (!b && !n) {printf("1\n"); continue;}
60     if (!b) {printf("no solution\n"); continue;}
61     LL ans=log_mod(b,n,P);
62     if (ans==-1){printf("no solution\n");continue;}
63     printf("%lld\n",ans);
64   }
65   return 0;
66 }

View Code