来画柿子吧
我们要求的是
[f(x)equiv t(mod p)
]
其中(f(1)=x_0,f(x)=af(x-1)+b)
我们来写几项柿子看看
[f(1)=x_0
]
[f(2)=ax_0+b
]
[f(3)=a(ax_0+b)+b=a^2x_0+ab+b
]
[f(4)=a^3x_0+a^2b+ab+b
]
我们发现好像后面就是一个等比数列求和啊
于是我们甚至可以搞出一个通项来
于是
[f(x)=a^{x-1}x_0+bsum_{i=0}^{x-2}a^i
]
显然后面那个东西就是(frac{a^{x-1}-1}{a-1})
所以
[f(x)=a^{x-1}x_0+frac{b imes a^{x-1}-b}{a-1}
]
干脆设(k=x-1)
[f(x)=frac{a^kx_0(a-1)+b imes a^k-b}{a-1}=frac{a^k(ax_0-x_0+b)-b}{a-1}
]
所以我们现在的方程是
[frac{a^k(ax_0-x_0+b)}{a-1}-frac{b}{a-1}equiv t(mod p)
]
我们设
[inv=inv(frac{ax_0-x_0+b}{a-1},p)
]
所以现在变成了
[a^kequiv (t+frac{b}{a-1}) imes inv(mod p)
]
所以这不就是(bsgs)板子了吗，(k+1)就是答案了
注意特判掉(a=1)以及(x_0=t)的情况
代码
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<tr1/unordered_map>
#define re register
#define LL long long
using namespace std::tr1;
unordered_map<LL,LL> ma;
int T;
LL P,a,b,x0,t;
void exgcd(LL a,LL b,LL &x,LL &y) {if(!b) {x=1,y=0;return;} exgcd(b,a%b,y,x);y-=a/b*x;}
inline LL quick(LL a,LL b) {LL S=1;while(b) {if(b&1) S=S*a%P; b>>=1; a=a*a%P;} return S;}
inline void bsgs()
{
if(x0==t) {puts("1");return;}
if(a==0) {if(b==t) puts("2");else puts("-1"); return;}
if(a==1&&!b) {puts("-1");return;}
if(a==1&&b)
{
t=t-x0; t=(t%P+P)%P;
LL x,y;
exgcd(b,P,x,y); x=(x*t%P+P)%P;
printf("%lld
",x+1); return;
}
ma.clear();
if(a%P==0) {puts("-1");return;}
LL inv=(a*x0%P-x0+b)%P; inv=(inv+P)%P;
LL x,y; exgcd(a-1,P,x,y); x=(x%P+P)%P; t=t+(b*x)%P; t%=P;inv=inv*x%P;
exgcd(inv,P,x,y);
x=(x%P+P)%P;
t=t*x%P;
LL now=1;
LL m=ceil(std::sqrt(P+1));
for(re int i=0;i<=m;i++) ma[now*t%P]=i,now=now*a%P;
LL S=quick(a,m);now=S;
for(re int i=1;i<=m;i++)
{
if(ma.find(now)!=ma.end())
{LL ans=(LL)i*(LL)m-ma[now];printf("%lld
",ans+1);return;}
now=now*S%P;
}
puts("-1");
}
int main()
{
scanf("%d",&T);
while(T--) scanf("%lld%lld%lld%lld%lld",&P,&a,&b,&x0,&t),bsgs();
return 0;
}