题意：
给定$a,b,p,x_1$，$\forall i>1,x_i = ax_{i-1} +b$。
求最小的$i$满足$x_i = t$，若无解则输出-1。
$0\leq a,b,x_1 , t<p\leq 10^{9},p是质数$。
题解：
挺水的一道题，展开之后BSGS即可。
但$a\leq 1$的地方需要特判，还巨复杂，有高中数学题内味了。
复杂度$O(\sqrt{p})$。
套路：
代码：
#include<bits/stdc++.h> #define maxn 200005 #define maxm 500005 #define inf 0x7fffffff #define ll long long #define rint register int #define debug(x) cerr<<#x<<": "<<x<<endl #define fgx cerr<<"--------------"<<endl #define dgx cerr<<"=============="<<endl using namespace std; ll p; unordered_map<ll,ll> M; inline ll read(){ ll x=0,f=1; char c=getchar(); for(;!isdigit(c);c=getchar()) if(c==‘-‘) f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-‘0‘; return x*f; } inline ll pw(ll a,ll b){ll r=1;while(b)r=(b&1)?r*a%p:r,a=a*a%p,b>>=1;return r;} inline ll inv(ll x){return pw(x,p-2);} inline ll BSGS(ll a,ll b){ M.clear(); ll n=ceil(sqrt(p)),ans=1ll<<62; for(ll i=0,t=1;i<=n;i++,t=t*a%p) M[b*t%p]=i; for(ll i=0,t=1,w=pw(a,n);i<=n;i++,t=t*w%p) if(M[t] && i*n-M[t]>=0) ans=min(ans,i*n-M[t]); if(ans==(1ll<<62)) return -1; else return ans; } int main(){ //freopen("P3306_2.in","r",stdin); //freopen("1.out","w",stdout); ll T=read(); while(T--){ p=read(); ll a=read(),b=read(),x1=read(),t=read(); if(a==0){ if(x1==t) printf("1\n"); else if(b==t) printf("2\n"); else printf("-1\n"); } else if(a==1){ if(b==0){ if(x1==t) printf("1\n"); else printf("-1\n"); } else printf("%lld\n",(t-x1+p)*inv(b)%p+1); } else{ if((x1+(b*inv(a-1)))%p==0){ if((t+(b*inv(a-1)))%p==0) printf("1\n"); else printf("-1\n"); } else{ ll y=(t+(b*inv(a-1)))%p*inv((x1+(b*inv(a-1)))%p)%p; ll ans=BSGS(a,y)+1; if(ans==0) printf("-1\n"); else printf("%lld\n",ans); } } } return 0; } //59 38 24 25 5
原文：https://www.cnblogs.com/YSFAC/p/13231571.html
