http://www.lydsy.com/JudgeOnline/problem.php?id=3122
题意:给出p,a,b,x1,t
已知xn=a*xn-1+b%p，求最小的n令xn=t
首先，若x1=t，则返回1
若a=0，则若b=t 返回2，否则无解
若a=1，则T=t-x1+p%p，可以列出方程
b*x+p*y==T % p
若a>=2，则根据等比数列和可得
xn=t=x1*a^(n-1)+b*(a^(n-1)-1)/(a-1) %p
由于p为质数，所以令c=inv[a-1]=(a-1)^(p-2)
x1*a^(n-1)+b*c*(a^(n-1))==b*c+t %p
(x1+b*c)*(a^(n-1))==b*c+t % p
令A=x1+b*c,B=p,C=b*c+t
则就是解A*X+B*Y==C %p
解出来X=a^(n-1),然后这个用BSGS求就可以了
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<map>
#define ll long long
ll p;
ll read(){
char ch=getchar();ll t=,f=;
while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}
while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}
return t*f;
}
ll Pow(ll x,ll y){
ll res=;
if (x<) x=(x+p)%p;
while (y){
if (y%) res=(res*x)%p;
x=(x*x)%p;
y/=;
}
return res;
}
ll gcd(ll a,ll b){
if (b==) return a;
else return gcd(b,a%b);
}
void exgcd(ll a,ll b,ll &x,ll &y){
if (b==){
x=;
y=;
return;
}
exgcd(b,a%b,x,y);
ll T=x;
x=y;
y=T-(a/b)*y;
}
ll reverse(ll X){
ll A=X,B=p;
ll x,y;
exgcd(A,B,x,y);
return (x%p+p)%p;
}
ll work(ll a,ll b){
a%=p;
if (a==){
if (b==) return ;
else return -;
}
std::map<ll,int> mp;
ll m=sqrt(p)+,I=,Im=Pow(a,p--m),t=;
mp.clear();mp[]=m+;
for (int i=;i<m;i++){
t=t*a%p;
if (!mp[t]) mp[t]=i;
}
for (int k=;k<m;k++){
int i=mp[I*b%p];
if (i){
if (i==m+) i=;
return i+k*m;
}
I=I*Im%p;
}
return -;
}
ll solve(ll a,ll b,ll x1,ll t){
if (t==x1) {
return ;
}
if (a==){
if (b==t){
return ;
}
return -;
}
if (a==){
ll A=b,B=p,T=(t-x1+p)%p;
ll D=gcd(A,B);
if (T%D) {
return -;
}
T/=D;
ll x,y;
exgcd(A,B,x,y);
x=(x*T)%p;
while (x<) x+=p;
return x+;
}
ll c=Pow(a-,p-);
ll A=(b*c+x1)%p,B=p,T=(b*c+t)%p;
if (A<) A=(A+p)%p;
if (B<) B=(B+p)%p;
ll D=gcd(A,B);
if (T%D){
return -;
}
T/=D;
ll x,y;
exgcd(A,B,x,y);
while (x<) x=(x+p)%p;
x=(x*T)%p;
ll ans=work(a,x);
if (ans!=-) return ans+;
else return ans;
}
int main(){
int Tcase;
scanf("%d",&Tcase);
while (Tcase--){
ll a,b,x1,t;
p=read();a=read();b=read();x1=read();t=read();
printf("%lld\n",solve(a,b,x1,t));
}
}