做题时间：2026.8.18 题目难度：提高 | 题目链接 | 洛谷链接

老实了，$2$ 分钟秒掉的思路，$5$ 分钟写好的代码，结果调了 $30$ 分钟。

首先题解的所有运算均在模 $P$ 的情况下进行。

分析题目，定义 $f(x)=Ax+B$，题目即求最小的 $x$ 满足 $f^x(S)=G$。

先打表：

$$f(S)=AS+B$$ $$f^2(S)=A^2S+AB+B$$ $$...$$ $$f^x(S)=A^xB+\sum_{i=0}^{x-1} A^iB$$

那么非常容易就可以得到：

$$f^{x+1}(S)-f^x(S)=A^{x+1}S+A^xB-A^xS$$

又得知 $f(G)-G=AG+B-G$

代入 $G=f^x(S)$ 得：

$$A^{x+1}S+A^xB-A^xS=AG+B-G$$

即：

$$A^x(AS+B-S)=AG+B-G$$

将 $AS+B-S$ 移到右边，得：

$$A^x=\frac{AG+B-G}{AS+B-S}$$

右边部分可以用逆元解决，然后聪明的小朋友就去用 BSGS 了，喜提 $0$ 分。连样例都过不去

这是为什么呢？

因为 BSGS 只能解决 $A > 1$ 的情况。所以 $A=0$ 得直接特判，$A=1$ 用 exgcd。

好了，现在有 $3$ 分了。因为会出现 $AS+B-S=0$ 的情况，你还得特判。

最后就可以过了。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int bsgs(int a,int b,int p)
{
	a%=p,b%=p;if(b==1)return 0;
	int m=ceil(sqrt(p)),am=1;
	unordered_map<int,int>f;
	for(int i=1;i<=m;i++)f[b*(am=am*a%p)%p]=i;
	for(int i=1,t=1;i<=m;i++)if(f.count(t=t*am%p))return i*m-f[t];
	return -1;
}
void exgcd(int a,int b,int &d,int &x,int &y)
{
	if(b==0){d=a,x=1,y=0;return;}
	exgcd(b,a%b,d,y,x);
	y-=a/b*x;
}
int qpow(int a,int b,int p){int ans=1;for(;b;b>>=1,a=a*a%p)if(b&1)ans=ans*a%p;return ans;}
void solve()
{
	int p,a,b,s,g;cin>>p>>a>>b>>s>>g;
	if(a==0)
	{
		if(s==g)cout<<0<<'\n';
		else if(b==g)cout<<1<<'\n';
		else cout<<-1<<'\n';
		return ;
	}
	if(a==1)
	{
		int d,x,y,K=((g-s)%p+p)%p;
		exgcd(b,p,d,x,y);
		if(K%d!=0)cout<<-1<<'\n';
		else
		{
			int dx=abs(p/d);
			x=(x*(K/d)%dx+dx)%dx;
			cout<<x<<'\n';
		}
		return;
	}
	int p1=((a*g+b-g)%p+p)%p,p2=((a*s+b-s)%p+p)%p;
	if(p1==0&&p2==0)cout<<0<<'\n';
	else if(p1!=0&&p2==0)cout<<-1<<'\n';
	else
	{
		int ans=bsgs(a,(p1)%p*qpow(p2,p-2,p)%p,p);
		cout<<ans<<'\n';
	}
}
signed main()
{
	int t;cin>>t;
	while(t--)solve();
	return 0;
}