本文共 1883 字，大约阅读时间需要 6 分钟。
一题更比三题强
1操作直接裸的快速幂
2操作用exgcd求出最小正整数解
3操作用BSGS硬上
然后没有然后了
1 //minamoto 2 #include 3 #include 4 #include 5 #include 6 #define ll long long 7 using namespace std; 8 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 9 char buf[1<<21],*p1=buf,*p2=buf;10 inline ll read(){11 #define num ch-'0'12 char ch;bool flag=0;ll res;13 while(!isdigit(ch=getc()))14 (ch=='-')&&(flag=true);15 for(res=num;isdigit(ch=getc());res=res*10+num);16 (flag)&&(res=-res);17 #undef num18 return res;19 }20 inline ll ksm(ll a,ll b,ll p){21 ll res=1;22 while(b){23 if(b&1) (res*=a)%=p;24 (a*=a)%=p,b>>=1;25 }26 return res;27 }28 ll exgcd(ll a,ll b,ll &x,ll &y){29 if(!b){x=1,y=0;return a;}30 ll d=exgcd(b,a%b,x,y);31 ll t=x;x=y,y=t-y*(a/b);32 return d;33 }34 map mp;35 ll BSGS(ll a,ll b,ll p){36 mp.clear();37 b%=p;int t=sqrt((double)p)+1,tot=1;38 for(int j=0;j =0&&i*t-j>=0) return i*t-j;47 tot=tot*a%p;48 }49 return -1;50 }51 ll t,k,z,y,p;52 void solve1(){53 while(t--){54 y=read(),z=read(),p=read();55 printf("%lld\n",ksm(y,z,p));56 }57 }58 void solve2(){59 while(t--){60 y=read(),z=read(),p=read();61 ll x=0,yy=0,d=0;62 d=exgcd(y,p,x,yy);63 if(z%d!=0){puts("Orz, I cannot find x!");}64 else{65 ll tmp=abs(p/d);66 x=(((x*z)/d)%tmp+tmp)%tmp;67 printf("%lld\n",x);68 }69 }70 }71 void solve3(){72 while(t--){73 y=read(),z=read(),p=read();74 ll ans=BSGS(y,z,p);75 if(ans!=-1) printf("%lld\n",ans);76 else puts("Orz, I cannot find x!");77 }78 }79 int main(){80 // freopen("testdata.in","r",stdin);81 t=read(),k=read();82 switch(k){83 case 1:solve1();break;84 case 2:solve2();break;85 case 3:solve3();break;86 }87 return 0;88 }
转载于:https://www.cnblogs.com/bztMinamoto/p/9740717.html