思路
题目给出了一个数列
\[x_{i+1}\equiv {a\times x_i+b}\pmod{p} \]并想要求最小的 \(x_i=G\)，那我们可以考虑求出这个数列的通项公式。
具体的，观察到原式可以转化成一个等比数列的形式，所以我们可以先设一个常数 \(k\)，使得
\[x_{i+1}+k=a(x_i+k) \]替换进原先的式子
\[a(x_i+k)-k ax_i+b \]\[ak-k=b \]\[k=\frac{b}{a-1} \]于是就有
\[x_{i+1}+\frac{b}{a-1}=a\left( x_i+\frac{b}{a-1} \right) \]这样就把原式化成等比数列的形式了
\[x_{i+1}+\frac{b}{a-1}\equiv a\left( x_i+\frac{b}{a-1} \right) \pmod p \]由等比数列的通项公式得
\[x_n+\frac{b}{a-1}\equiv a^{n}\times \left( x_0+\frac{b}{a-1} \right)\pmod p \]题目是求 \(n\)，移个项
\[a^{n}\equiv \frac{{x_n+\frac{b}{a-1}}}{x_0+\frac{b}{a-1}} \]然后求下逆元就能 BSGS 了。
代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
inline int read();
int T;
long long p,a,b,x0,xn;
long long ksm(long long a,long long b,long long p)
{
long long ans=1;
while(b)
{
if(b&1) ans=(a*ans)%p;
a=(a*a)%p;
b>>=1;
}
return ans;
}
long long bsgs(long long a,long long b,long long p)
{
map<int,int> ma;ma.clear();
b%=p;
int t=sqrt(p)+1;
for(int i=0;i<=t;i++)
{
int val=b*ksm(a,i,p)%p;
ma[val]=i;
}
a=ksm(a,t,p);
for(int i=0;i<=t;i++)
{
int val=ksm(a,i,p);
int j=ma.find(val)==ma.end()?-1:ma[val];
if(j>0&&i*t-j>=0) return i*t-j;
}
return -1;
}
int main()
{
T=read();
while(T--)
{
p=read();a=read();b=read();x0=read();xn=read();
if(x0==xn)
{
puts("0");
continue;
}
if(a==0)
{
if(xn==b) puts("1");
else puts("-1");
continue;
}
if(a==1&&b==0)
{
puts("-1");
continue;
}
if(a==1)
{
long long ans=((xn-x0)%p+p)%p*ksm(b,p-2,p)%p;
printf("%lld\n",ans);
continue;
}
long long inv=b%p*ksm(a-1,p-2,p)%p;
long long b1=(xn%p+inv)%p;
long long b2=ksm(x0%p+inv,p-2,p)%p;
int ans=bsgs(a,b1*b2%p,p);
printf("%d\n",ans);
}
return 0;
}
inline int read()
{
int x=0,f=1;
char ch;
ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-') f=-f;ch=getchar();}
while(ch<='9'&&ch>='0')
{
x=(x<<1)+(x<<3)+(ch&15);
ch=getchar();
}
return x*f;
}