、
(0le ale P−1,0le ble P−1,2le Ple 10^9)
Sample Input
3
7 1 1 3 3
7 2 2 2 0
7 2 2 2 1
Sample Output
1
3
-1
推一下前几项就能知道：
[x_nequiv tequiv a^{n-1}x_1+bsum_{i=0}^{n-2}a^ipmod p
]
[tequiv a^{n-1}x_1+bfrac{a^{n-1}-1}{a-1}pmod p
]
然后肯定要求逆元，我们设((a-1)^{-1}=inv)
那么原式：
[tequiv a^{n-1}x_1+ba^{n-1}cdot inv-bcdot invpmod p
]
[t+bcdot invequiv a^{n-1}(x_1+bcdot inv)pmod p
]
[a^{n-1}equiv frac{t+bcdot inv}{x_1+bcdot inv}pmod p
]
所以此时只要求出那个分母的逆元，然后用 BSGS 就行了
但是注意 BSGS 得到的答案要加一，但此时不能再取模了，不然成(0)显然不合理
然后开始烦人的特判
- (x_1=t ightarrow n=1)
- (a=0)，则只需判断是不是(b=t)，如果是那么第二天就能读到，不然永远读不到
- (a=1
ightarrow tequiv x_nequiv x_1+b(n-1))，此时还要分两种：
- (b=0)，无解，因为前面已经判定过是不是(x_1=t)了，所以现在肯定是不相等
- (n=dfrac{t-x_1}{b}+1)，此时为了防止模成(0)，再乘逆元的时候取一次模，后面的加一仍然不取模
这些虽然不难但不看题解我还是没有想全
还有一个问题，就是 BSGS 的时候，求解(a^xequiv npmod p)，不能判断(pmid a)就立刻返回无解，因为如果此时(n=0)，那么是要返回(0)的
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<cstring>
#define reg register
#define EN std::puts("")
#define LL long long
inline int read(){
register int x=0;register int y=1;
register char c=std::getchar();
while(c<'0'||c>'9'){if(c=='-') y=0;c=std::getchar();}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=std::getchar();}
return y?x:-x;
}
std::map<LL,LL>map;
inline int power(int a,int b,int p){
int ret=1;
while(b){
if(b&1) ret=1ll*ret*a%p;
b>>=1;a=1ll*a*a%p;
}
return ret;
}
inline LL BSGS(LL a,LL n,LL p){
if(!(a%p)){
if(n) return -1;
else return 0;
}
map.clear();
reg LL m=std::ceil(std::sqrt(p));
for(reg LL i=0,s=n;i<m;i++,s=s*a%p) map[s]=i;
for(reg LL i=1,s=power(a,m,p),tmp=s;i<=m;i++,s=s*tmp%p)
if(map.find(s)!=map.end()) return i*m-map[s];
return -1;
}
int main(){int T=read();while(T--){
LL p=read(),a=read(),b=read(),x1=read(),t=read();
if(x1==t) std::puts("1");
else if(!a) std::puts(b==t?"2":"-1");
else if(a==1){
if(!b) std::puts("-1");
else{
t=(t-x1+p)%p;
std::printf("%lld
",(t*power(b,p-2,p)%p)+1);
}
}
else{
LL inv=power(a-1,p-2,p);
t=(t+(b*inv%p))%p;
LL ans=BSGS(a,t*power((x1+(b*inv%p))%p,p-2,p)%p,p);
if(~ans) std::printf("%lld
",ans+1);
else std::puts("-1");
}
}
return 0;
}