题目链接：随机数生成器
经典数学题……
为了方便接下来的处理，我们可以先把\(X_1=t\)的情况特判掉。
当\(a=0\)的时候显然只需再判一下\(b\)是否等于\(t\)即可。
当\(a=1\)的时候就变成了一次的同余方程，直接用拓展欧几里得解出来即可。
当\(a>1\)的时候可以等比数列求和，对于\(i>1\)，得到\(X_i=a^{i-1}X_1+\frac{a^{i-1}-1}{a-1}b\)。
由于\(p\)是质数，那么\(a-1\)就有逆元。于是移下项，最后剩下一个形如\(a^{i-1}\equiv y \pmod p\)的方程，大步小步解出来即可。
下面贴代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
#define mod 2000029 using namespace std;
typedef long long llg; int T,a,b,x1,t,p;
struct hash{
int head[mod],next[mod],c[mod],tt,d[mod],ld;
int to[mod]; bool vis[mod];
int find(int now){
int u=now%mod;
for(int i=head[u];i;i=next[i])
if(to[i]==now) return i;
return 0;
}
void insert(int now,int i){
int u=now%mod,v;
if((v=find(now))){c[v]=i;return;}
if(!vis[u]) vis[u]=1,d[++ld]=u; c[++tt]=i;
to[tt]=now; next[tt]=head[u]; head[u]=tt;
}
void finalize(){
for(int i=1;i<=ld;i++) vis[d[i]]=0,head[d[i]]=0;
ld=0; tt=0;
}
}A; int gcd(int x,int y){
int r=x%y;
while(r) x=y,y=r,r=x%y;
return y;
} int exgcd(int a,int b,int &x,int &y){
if(!b){x=1;y=0;return a;}
int aa=exgcd(b,a%b,x,y),bb=x;
x=y; y=bb-1ll*(a/b)*y%p; if(y<0) y+=p;
return aa;
} int mi(int a,int b){
int s=1;
while(b){
if(b&1) s=1ll*s*a%p;
a=1ll*a*a%p; b>>=1;
}
return s;
} int main(){
File("a");
scanf("%d",&T);
while(T--){
scanf("%d %d %d %d %d",&p,&a,&b,&x1,&t);
if(x1==t){printf("1\n");continue;}
if(a==0) printf(b==t?"2\n":"-1\n");
else if(a==1){
int X=t-x1,x,y,q;
if(X<0) X+=p; q=exgcd(b,p,x,y);
if(X%q) printf("-1\n");
else{
x=1ll*x*(X/q)%p; x%=1ll*(p/q)*(b/q);
printf("%d\n",x+1);
}
}
else{
b=1ll*b*mi(a-1,p-2)%p; t+=b;
t=1ll*t*mi(x1+b,p-2)%p;
int N=sqrt(p)+1,y=mi(a,N),ans=p+1;
for(int i=0,x=t;i<N;i++) A.insert(x,i),x=1ll*x*a%p;
for(int i=1,j=N,x=y,u;j<=p+N;j+=N,i++,x=1ll*x*y%p)
if((u=A.find(x))) ans=min(ans,i*N-A.c[u]);
if(ans==p+1) printf("-1\n");
else printf("%d\n",ans+1);
A.finalize();
}
}
return 0;
}