【BZOJ】【2242】【SDOI2011】计算器

Arce

快速幂/扩展欧几里得/BSGS经典好例题！！
三个问题三种算法……
算法：白书（算法竞赛入门经典——训练指南）全有……

1 /**************************************************************
 2   Problem: 2242
 3   User: Tunix
 4   Language: C++
 5   Result: Accepted
 6   Time:1824 ms
 7   Memory:2476 kb
 8 ****************************************************************/
 9  
10 //BZOJ 2242
11 #include<map>
12 #include<cmath>
13 #include<cstdio>
14 #include<cstdlib>
15 #include<cstring>
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  
23 int getint(){
24   int v=0,sign=1; char ch=getchar();
25   while(ch<'0'||ch>'9') {if (ch=='-') sign=-1; ch=getchar();}
26   while(ch>='0'&&ch<='9') {v=v*10+ch-'0'; ch=getchar();}
27   return v*=sign;
28 }
29 /*******************tamplate********************/
30 typedef long long LL;
31 LL x,y,z,P;
32 LL pow(LL a,LL b,LL P){
33   LL r=1,base=a;
34   while(b){
35     if (b&1) r=r*base%P;
36     base=base*base%P;
37     b>>=1;
38   }
39   return r;
40 }
41 void exgcd(LL a,LL b,LL &d,LL &x,LL &y){
42   if (!b) {d=a; x=1; y=0; return;}
43   else{exgcd(b,a%b,d,y,x); y-=x*(a/b);}
44 }
45 LL log_mod(LL a,LL b,LL P){
46   LL m,v,e=1,i;
47   m=ceil(sqrt(P+0.5));//这里需要用ceil……？
48   v=pow(a,P-m-1,P);//inv
49   map<LL,LL> x;
50   x[1]=0;
51   for(int i=1;i<m;++i){
52     e=e*a%P;
53     if (!x.count(e)) x[e]=i;
54   }
55   rep(i,m){
56     if (x.count(b)) return (LL)i*m+x[b];
57     b=b*v%P;
58   }
59   return -1;
60 }
61 int main(){
62   int T=getint(),K=getint();
63   while(T--){
64     y=getint(); z=getint(); P=getint();
65     if (K==1) printf("%lld\n",pow(y,z,P));
66     if (K==2){
67       LL d=0,X=0,Y=0;
68       exgcd(y,P,d,X,Y);
69       if(z%d){ printf("Orz, I cannot find x!\n"); continue; }
70       X*=z/d;
71       LL T=X*d/P;
72       X-=T*P/d;
73       if (X<0) X+=P/d;
74       printf("%lld\n",X);
75     }
76     if (K==3){
77       y%=P; z%=P;
78       if(!y && !z) {printf("1\n"); continue;}
79       if(!y) { printf("Orz, I cannot find x!\n"); continue; }
80       LL ans=log_mod(y,z,P);
81       if (ans==-1){ printf("Orz, I cannot find x!\n"); continue; }
82       printf("%lld\n",ans);
83     }
84   }
85   return 0;
86 }

View Code