输出不一样啊，At里答案要 -1
by Konjac_16 @ 2022-09-27 20:39:49
@[Konjac_16](/user/538521) 呜。。。。挂错代码了。。。抱歉
[Code](https://www.luogu.com.cn/paste/00zkfaat)
by 淸梣ling @ 2022-09-27 20:41:50
不清楚，加了几个特判还是没过，可能是 bsgs 写挂了，比如哪块没取模之类的
by Konjac_16 @ 2022-09-27 21:04:52
@[Konjac_16](/user/538521) 矩阵能直接套 BSGS 的模板吗？
by 淸梣ling @ 2022-09-27 21:17:39
@[淸梣ling](/user/239192) 我是直接化的式子，然后直接用 bsgs
by Konjac_16 @ 2022-09-27 21:19:24
@[淸梣ling](/user/239192) 我没这么写过，不太清楚
by Konjac_16 @ 2022-09-27 21:19:49
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mid ((l+r)>>1)
// #define mod (998244353)
#define eps (1e-9)
#define mk make_pair
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define rep(i,a,b) for(int i=(a);i>=(b);--i)
inline namespace IO{
inline int read(){
int x=0;int f=1;char ch;
while((ch=getchar())<'0'||x>'9')if(ch=='-')f=-1;
while(ch>='0'&&ch<='9'){x=((x<<1)+(x<<3)+(ch^48)),ch=getchar();}
return x*f;
}
void write(char x){putchar(x);}
void write(const char *x){for(;*x;++x)putchar(*x);}
void write(char *x){for(;*x;++x)putchar(*x);}
void write(signed x){
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10); putchar('0'+x-x/10*10);
}
void write(long long x){
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10); putchar('0'+x-x/10*10);
}
void write(unsigned long long x){
if(x>9)write(x/10);
putchar('0'+x-x/10*10);
}
void write(double x){printf("%0.3lf",x);}
void write(const string &s){cout<<s;}
template<typename type1,typename type2,typename ...typen>
void write(type1 a1,type2 a2,typen ...an){
write(a1);
write(a2,an...);
}
}using namespace IO;
inline int gcd(int x,int y){return y==0?x:gcd(y,x%y);}
inline int lcm(int x,int y){return x/gcd(x,y)*y;}
const int N=200005;
int mod;
inline int qpow(int a,int b){
int res=1;
for(;b;b>>=1){
if(b&1)res=res*a%mod;
a=a*a%mod;
}
return res;
}
unordered_map<int,int> mp;
inline int bsgs(int a,int b){
mp.clear(); b%=mod;
// write(a,' ',b,'\n');
int t=sqrt(mod-1)+1;
For(i,0,t-1){
int v=b*qpow(a,i)%mod; mp[v]=i;
}
a=qpow(a,t);
// if(!a)return b==0?1:-1;
For(i,0,t){
int v=qpow(a,i);
if(mp.find(v)==mp.end())continue;
int j=mp[v];
if(j>=0&&i*t-j>=0)return i*t-j;
}
return -1;
}
inline void work(){
mod=read();
int A=read(),B=read(),S=read(),G=read();
if(S==G){write(0,'\n');return;}
if(A==0){
if(G==B%mod)write(1,'\n');
else write(-1,'\n');
return;
}
if(A==1){
if(B==0){write(-1,'\n');return;}
int res=(G-S+mod)%mod*qpow(B,mod-2)%mod;
write(res,'\n'); return;
}
int Up=((A-1)*G+B)%mod;
int Down=B+(A-1)*S%mod;
// write(Up,' ',Down,'\n');
// if(Up%Down!=0){write(-1,'\n');return;}
int res=bsgs(A,Up*qpow(Down,mod-2));
write(res,'\n');
}
signed main()
{
// cout<<54%11<<'\n';
int T=read();
while(T--)work();
return 0;
}
/*
1
2 0 1 1 1
1
5 2 1 1 0
*/
```
by Konjac_16 @ 2022-09-27 21:20:13
@[淸梣ling](/user/239192) 感谢大佬的AT原题，洛谷的数据果然太水，连蒟蒻的垃圾代码都能过。\
实测`a==1`（会使推导过程分母为0）,`a==0`（会出现0的0次方）,`/*分母*/%p==0`（逆元不存在）三个特判可以AC
by felixesintot @ 2023-08-11 23:02:48