Description
.jpg)
Hint
(p in [2,10^9]) 且为质数。
保证 (X_1) 和 (t) 都是合法的页码。
Solution
根据递推关系，得：
[X_2 equiv a cdot X_1 + b pmod p
]
[X_3 equiv a cdot X_2 + b equiv a^2 cdot X_1 + ab + b pmod p
]
[X_4 equiv a cdot X_3 + b equiv a^3 cdot X_1 + a^2b + ab + b pmod p
]
[cdots cdots
]
[X_n equiv a^{n-1} cdot X_1 + b imes sumlimits_{i=0}^{n-2} a^i pmod p
]
我们发现 (sum_{i=0}^{n-2} a^i) 就是一个等比数列求和，那么：
[X_n equiv a^{n-1} cdot X_1 + b imes dfrac{1 - a^{n-1}}{1 - a} pmod p
]
[X_n equiv a^{n-1} cdot X_1 - dfrac{a^{n-1}}{1 - a} + dfrac{b}{1 - a} pmod p
]
[X_n equiv a^{n-1} cdot (X_1 - dfrac{1}{1 - a}) + dfrac{b}{1 - a} pmod p
]
[a^{n-1} cdot (X_1 - dfrac{1}{1 - a}) equiv X_n - dfrac{b}{1 - a} pmod p
]
[a^{n-1} equiv dfrac{X_n - dfrac{b}{1 - a}}{X_1 - dfrac{1}{1 - a}} pmod p
]
而这个 (X_n) 其实就是题目中的 (t) ，那么我们就是要求关于 (n) 方程
[a^{n-1} equiv dfrac{t - dfrac{b}{1 - a}}{X_1 - dfrac{1}{1 - a}} pmod p
]
的这些非负整数解（如果有解的话）。
我们惊喜地发现这里只有 (n) 一个未知数，那么显然可以用 BSGS （这里 (p) 为质数）求解。
但这里还有不少需要注意的细节：
- 当 (t = X_1) 时，答案为 (0) 。
- 当 (a = 0) 时，(X_i equiv b pmod p)，其中 (i > 1)。
- 当 (a = 1) 时，(X_i equiv b(i-1) pmod p)，那么这就是一个线性同余方程，直接求逆元即可。
注意式子中的所有除法都是逆元。
/*
* Author : _Wallace_
* Source : https://www.cnblogs.com/-Wallace-/
* Problem : BZOJ 3122 SDOI2013 随机数生成器
*/
#include<cmath>
#include<iostream>
#include<tr1/unordered_map>
typedef long long LL;
typedef std::tr1::unordered_map<LL,LL> HashMap;
using std::cin;
using std::cout;
using std::endl;
LL fastpow(LL a,LL b,LL c) {
if(!b) return 1ll%c;
LL t=fastpow(a,b>>1,c);
if(b&1) return t*t%c*a%c;
else return t*t%c;
}
LL inverse(LL a,LL p) {
return fastpow(a,p-2,p);
}
HashMap f;
inline LL BSGS(LL a,LL b,LL p) {
f.clear();
LL m=ceil(sqrt(p));
b%=p;
for(LL i=1;i<=m;i++)
(b*=a)%=p,f[b]=i;
LL t=fastpow(a,m,p);
b=1;
for(LL i=1;i<=m;i++) {
(b*=t)%=p;
if(f.count(b))
return (i*m-f[b]+p)%p;
}
return -1;
}
signed main() {
LL p,a,b,x1,t;
int Test_c;
cin>>Test_c;
while(Test_c--) {
cin>>p>>a>>b>>x1>>t;
if(x1==t) {
cout<<1<<endl;
} else if(a==0) {
if(b==t) cout<<2<<endl;
else cout<<-1<<endl;
} else if(a==1) {
if(b==0) cout<<-1<<endl;
else cout<<((t-x1)%p+p)%p*inverse(b,p)%p+1<<endl;
} else {
LL tmp=((b*inverse(a-1,p)%p+t)%p)%p*inverse((b*inverse(a-1,p)%p+x1)%p,p)%p;
LL ans=BSGS(a,tmp,p);
if(ans==-1) cout<<-1<<endl;
else cout<<ans+1<<endl;
}
}
}