洛咕 P3306 [SDOI2013]随机数生成器

---

大力推式子？？？

\(X_{i}=\underbrace{a(a(\cdots(a(a}_{i-1个a}X_1+b)))\cdots)\)

\(=b+ba+ba^2+\cdots+ba^{i-3}+ba^{i-2}+X_1a^{i-1}\equiv t(\text{mod }p)\)

\(b\frac{a^{i-1}-1}{a-1}+a^{i-1}x_1\equiv t(\text{mod }p)\)

拆分一波，提出\(a^{i-1}\)

\((X_1+\frac{b}{a-1})a^{i-1}\equiv \frac{b}{a-1}+t(\text{mod }p)\)

\(a^{i-1}\equiv \frac{\frac{b}{a-1}+t}{\frac{b}{a-1}+X_1} (\text{mod }p)\)

然后bsgs即可。

这题还要加一堆特判。。。懒得写了。。。丧心病狂

#include
    
     #define il inline#define vd voidtypedef long long ll;il int gi(){    int x=0,f=1;    char ch=getchar();    while(!isdigit(ch)){        if(ch=='-')f=-1;        ch=getchar();    }    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();    return x*f;}ll T,mod,a,b,X1,t;il ll pow(ll a,ll b){    ll ret=1;    while(b){        if(b&1)ret=ret*a%mod;        a=a*a%mod;b>>=1;    }    return ret;}std::map
     
      M;int main(){#ifndef ONLINE_JUDGE    freopen("3306.in","r",stdin);    freopen("3306.out","w",stdout);#endif    T=gi();    while(T--){        mod=gi(),a=gi(),b=gi(),X1=gi(),t=gi();        ll B=(t+b*pow(a-1,mod-2)%mod)%mod,A=(B-t+X1+mod)%mod,C=B*pow(A,mod-2)%mod;        ll s=sqrt(mod)+1,ans=1e18;        if(t==X1){puts("1");continue;}        if(a==1){            A=b,B=(t-X1+mod)%mod;            if(b==0||A%std::__gcd(B,mod))puts("-1");            else printf("%lld\n",((t-X1+mod)*pow(b,mod-2)%mod)%mod+1);            continue;        }        if(a==0){printf("%lld\n",b==t?2ll:(-1ll));continue;}        M.clear();        for(ll i=0,j=C%mod;i