公式其实挺容易推的，看见zyf推的好复杂= =，其实直接代秦九昭算法，然后用等比数列求和就能推出来，推到最后应该是 Xn+b/a−1≡an−1(X1+b/a−1)(modp) 然后会发现除了a^n-1其他都是常数，注意要求逆元 然后直接BSGS就好了，求逆元可以用exgcd也可以用a^(p-2)求. 代码找不到了/(ㄒoㄒ)/~~，我贴zyf神犇的好了毕竟模板都是照着她写的.
#include<iostream>#include<cstring>#include<cstdio>#include<cmath>#include<map>using namespace std;#define LL long longLL T,P,a,b,x1,t;LL ny1,ny2,val1,val2,val3;LL ans;map <LL,LL> hash;inline LL fast_pow(LL a,LL p){ LL ans=1; for (;p;p>>=1,a=a*a%P) if (p&1) ans=ans*a%P; return ans;}inline LL BSGS(LL a,LL b){ LL m=ceil(sqrt(P)); LL a_m=fast_pow(a,m); hash.clear(); LL mul=1; LL val=mul*b%P; hash[val]=0; for (LL j=1;j<=m;++j){ mul=mul*a%P; val=mul*b%P; hash[val]=j; } mul=1; for (LL i=1;i<=m;++i){ mul=mul*a_m%P; if (hash[mul]){ LL x=i*m-hash[mul]; return x+1; } } return -1;}int main(){ scanf("%lld",&T); while (T--){ scanf("%lld%lld%lld%lld%lld",&P,&a,&b,&x1,&t); //一坨特判 if (t==x1){ PRintf("1/n"); continue; } if (a==0){ if (t==b) printf("2/n"); else printf("-1/n"); continue; } if (a==1&&b==0){ printf("-1/n"); continue; } if (a==1){ int nyb=fast_pow(b,P-2); ans=((((t-x1)%P+P)%P)*nyb%P)%P; printf("%lld/n",ans+1); continue; } ny1=fast_pow(a-1,P-2); val1=b*ny1%P; val2=(x1%P+val1)%P; ny2=fast_pow(val2,P-2); val3=(t+val1)%P; b=(val3*ny2)%P; ans=BSGS(a,b); printf("%lld/n",ans); }}新闻热点
疑难解答
