公式其實挺容易推的，看見zyf推的好復(fù)雜= =，其實直接代秦九昭算法，然后用等比數(shù)列求和就能推出來，推到最后應(yīng)該是 Xn+b/a?1≡an?1(X1+b/a?1)(modp) 然后會發(fā)現(xiàn)除了a^n-1其他都是常數(shù)，注意要求逆元 然后直接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){新聞熱點
疑難解答
