/*
已知递推数列 F[i]=a*F[i-1]+b (%c)
解方程F[x]=t
an+1 = b*an + c
an+1 + c/(b-1) = b(an + c/(b-1))
an+1 + c/(b-1) = b^(n-1) * (a1+c/(b-1))
根据这个数列可得
F[x] = (F[1] + b/(a-1))*a^(x-1) - b/(a-1) = t;
(F[1] + b/(a-1))*a^(x-1) = t+b/(a-1)
a^(x-1) = (t+b/(a-1)) / (F[1]+b/(a-1))
用逆元算出右边，再用bsgs算x即可
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll p,a,b,f1,t;
ll Pow(ll a,ll b,ll p){
ll res=
1;
while(b){
if(b%
2)
res=res*a%
p;
b>>=
1;a=a*a%
p;
}
return res;
}
ll inv(ll x,ll p){
return Pow(x,p-
2,p);
}
ll bsgs(ll a,ll b, ll p){
//用来求a^x=b, 令x=i*t-j,(a^t)^i = b*a^j
//先把右边的t个值存下来
map<ll,ll>
hash;
hash.clear();
b%=
p;
ll t=sqrt(p)+
1;
ll tmp=
b;
for(ll j=
0;j<t;j++
){
ll val=b*Pow(a,j,p)%
p;
hash[val]=
j;
}
a=
Pow(a,t,p);
if(a==
0)
return b==
0?
1:-
1;
for(
int i=
1;i<=t;i++
){//这个地方把循环起点改为1
ll val=
Pow(a,i,p);
int j=hash.find(val)==hash.end()?-
1:hash[val];
if(j>=
0 && i*t-j>=
0)
return i*t-
j;
}
return -
1;
}
//F[i]=a*F[i-1]+b (%c)
int main(){
int T;cin>>
T;
while(T--
){
cin>>p>>a>>b>>f1>>
t;
if(f1==t){puts(
"1");
continue;}
if(a==
0){
if(t==b)puts(
"2");
else puts(
"-1");
continue;
}
if(a==
1){
if(b==
0){puts(
"-1");
continue;}
ll ans = (((t-f1)%p+p)%p*inv(b,p))%
p;
cout<<ans+
1<<
'\n';
continue;
}
a%=p;b%=p;f1%=p;t%=
p;
ll tmp=b*inv(a-
1,p)%
p;
t=(t+tmp)%
p;
t=t*inv(f1+tmp,p)%
p;
t=t*a%
p;
cout<<bsgs(a,t,p)<<
'\n';
}
}
转载于:https://www.cnblogs.com/zsben991126/p/11016241.html
