本文共 1305 字，大约阅读时间需要 4 分钟。
/*bzoj2480*/#include #include #include #include #include typedef long long LL;std::map mmp;inline LL Pow(LL x,LL y,LL P){ LL ret=1; while(y){ if(y&1)ret=ret*x%P; x=x*x%P,y>>=1; } return ret;}inline LL gcd(LL x,LL y){ return x==0?y:gcd(y%x,x);}inline LL BSGS(LL A,LL B,LL C,LL D){ int len=ceil(sqrt(C+0.5)); LL temp=B,sum=D; mmp.clear(); for(int i=1;i<=len;++i)mmp[temp=temp*A%C]=i; temp=Pow(A,len,C); for(int i=1;i<=len;++i){ sum=sum*temp%C; if(mmp.count(sum))return i*len-mmp[sum]; } return -1;}inline LL exBSGS(LL A,LL B,LL C){/*A>=0(这里涉及到0^0是否有意义(是否为1),我们假设他是1好了) B>=0 C>0(%0和/0是一个效果啊)*//*假设我们求的解是最小自然数(无解输出-1)*/ if(C==1)return 0; A%=C,B%=C; if(B==1)return 0;/*判掉了解为0的情况*/ if(A==0){ if(B==0)return 1; return -1; }/*现在A>0 B>=0 B!=1 C>1*/ LL D=1;int cnt=0; for(LL g=gcd(A,C);g!=1;g=gcd(A,C)){ if(B%g!=0)return -1; C/=g,B/=g,D=D*(A/g)%C,++cnt; if(D==B)return cnt; }/*得到的C一定不为1*/ A%=C;/*现在我们得到了A的cnt次方与C除去gcd后的结果(分别是D和C),并且现在A与C互质了*/ LL ret=BSGS(A,B,C,D); return ret==-1?-1:ret+cnt;}int main(){ LL a,p,b,ans; while(true){ scanf("%lld%lld%lld",&a,&p,&b); if(p==0)return 0; ans=exBSGS(a,b,p); if(ans==-1)puts("No Solution"); else printf("%lld\n",ans); }}
转载于:https://www.cnblogs.com/TSHugh/p/8393161.html