本文共 1048 字，大约阅读时间需要 3 分钟。
exBSGS~
就是多个约分
#include #include #include #include #include #include #include using namespace std;typedef long long LL;LL gcd(LL a,LL b){ if(a==0)return b; return gcd(b%a,a);}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;}map Hash;LL exBSGS(LL a,LL p,LL b){ a%=p;b%=p; if(b==1)return 0; LL d=gcd(a,p),v=1,cnt=0; while(d!=1) { if(b%d!=0)return -1; b/=d;p/=d; v=v*(a/d)%p; cnt++; if(b==v)return cnt; d=gcd(a,p); } //rf Hash.clear(); LL t=(LL(sqrt(double(p+1)))); LL k=1; for(int j=0;j =0)return t*i-j+cnt; } k=(k*a)%p; } return -1; }}int main(){// freopen("1.in","r",stdin);// freopen("1.out","w",stdout); LL a,p,b; while(scanf("%lld%lld%lld",&a,&p,&b)!=EOF) { if(a==0&p==0&&b==0)break; if(p==1)printf("0\n"); else { LL d=exBSGS(a,p,b); if(d==-1)printf("No Solution\n"); else printf("%lld\n",d); } } return 0;}
转载于:https://www.cnblogs.com/AKCqhzdy/p/9334490.html