模版大杂烩系列
第一问是快速幂
第二问拓展欧几里得
第三问BSGS
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<map> using namespace std; typedef long long LL; LL quick_pow(LL A,LL p,LL mod) { LL ret=1; while(p!=0) { if(p%2==1)ret=(ret*A)%mod; A=(A*A)%mod;p/=2; } return ret; } void solve1(int T) { while(T--) { LL y,z,p; scanf("%lld%lld%lld",&y,&z,&p); printf("%lld ",quick_pow(y,z,p)); } } //-------------------------------------- LL exgcd(LL a,LL b,LL &x,LL &y) { if(a==0) { x=0,y=1; return b; } else { LL tx,ty; LL d=exgcd(b%a,a,tx,ty); x=ty-b/a*tx; y=tx; return d; } } void solve2(int T) { while(T--) { LL yy,z,p; scanf("%lld%lld%lld",&yy,&z,&p); LL A=yy,B=p,K=z,x,y; LL d=exgcd(A,B,x,y); if(K%d!=0)printf("Orz, I cannot find x! "); else { x=(x*(K/d)%(B/d)+(B/d))%(B/d); printf("%lld ",x); } } } //---------------------------------------- map<LL,LL>Hash; LL BSGS(LL a,LL b,LL mod) { Hash.clear();b%=mod; LL t=(LL(sqrt(double(mod+1)))),k=1; for(int j=0;j<t;j++) { Hash[b*k%mod]=j;//b*a^j k=(k*a)%mod; } a=quick_pow(a,t,mod);//a^t if(a==0)return b==0?1:-1; else { LL k=1; for(int i=0;i<=t;i++) { if(Hash.find(k)!=Hash.end()) { LL j=Hash[k]; if(t*i-j>=0)return t*i-j; } k=(k*a)%mod; } return -1; } } void solve3(int T) { while(T--) { LL y,z,p; scanf("%lld%lld%lld",&y,&z,&p); if(y%p==0)printf("Orz, I cannot find x! "); else { LL d=BSGS(y,z,p); if(d==-1)printf("Orz, I cannot find x! "); else printf("%lld ",d); } } } int main() { int T,K; scanf("%d%d",&T,&K); if(K==1)solve1(T); else if(K==2)solve2(T); else if(K==3)solve3(T); return 0; }