BZOJ3122 [SDOI2013] 随机数生成器
已知 $a,b,X_1,p,t$ ，
给定递推公式 $X_{i+1}=(aX{i}+b)\mod p(i\ge 1)$ ，求最小的正整数i满足 $X_i=t$ ，p为质数。
题解
这道题需要分类讨论：
- 当$X_1=t$时，答案为1.
- 当a=0时，如果b=t，则答案为2，否则无解。
- 当a=1时，原题化为$X_1+ib\equiv t$,求最小正整数解，也就是$ib\equiv t-x_1$。
当a>1，显然
$$ \begin{split} X_i & = a^{i-1}X_1+b\times (1+a+a^2+...+a^{n-2})\\\\ & = a^{i-1}X_1+b\times \frac{a^{n-1}-1}{a-1}\\\\ & = a^{i-1}X_1+\frac{b\times a^{n-1}}{a-1}-\frac{b\times 1}{a-1}\\\\ & = a^{i-1}(X_1+\frac{b}{a-1})-\frac{b\times 1}{a-1}\equiv t(\mod p) \end{split} $$
，所以
$$(X_1+\frac{b}{a-1})a^{i-1}\equiv t+\frac{b\times 1}{a-1}(\mod p)$$
$$a^{i-1}\equiv \frac{t+\frac{b\times 1}{a-1}}{X_1+\frac{b}{a-1}}(\mod p)$$
$$a^{i-1}\equiv \frac{t(a-1)+b}{X_1(a-1)+b}(\mod p)$$
BSGS即可。
/*
Author: CNYALI_LK
LANG: C++
PROG: 3122.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#include<tr1/unordered_map>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
using namespace std;
const double eps=1e-8;
const double PI=acos(-1.0);
typedef long long ll;
template<class T>ll chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>ll chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
ll p,a,b,x1,t;
ll fpm(ll a,ll b){
ll c=1;
while(b){
if(b&1)c=c*a%p;
a=a*a%p;
b>>=1;
}
return c;
}
ll inv(ll a){
ll b=p-2,c=1;
while(b){
if(b&1)c=c*a%p;
a=a*a%p;
b>>=1;
}
return c;
}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll BSGS(ll a,ll b){
if(b==1)return 1;
ll m=ceil(sqrt(p));
tr1::unordered_map<ll,ll> mp;
for(ll i=1;i<=m;++i){
b=b*a%p;
mp.insert(make_pair(b,i));
}
b=1;
a=fpm(a,m);
for(ll i=1;i<=m;++i){
b=b*a%p;
if(mp.count(b))return i*m-mp[b]+1;
}
return -1;
}
int main(){
#ifdef cnyali_lk
freopen("3122.in","r",stdin);
freopen("3122.out","w",stdout);
#endif
ll T;
scanf("%lld",&T);
while(T){
--T;
scanf("%lld%lld%lld%lld%lld",&p,&a,&b,&x1,&t);
if(x1==t)printf("1\n");
else
if(a==0){
if(b==t)printf("2\n");
else printf("-1\n");
}
else if(a==1){
if(!b)printf("-1\n");
else{
t=(t-x1+p)%p;
printf("%lld\n",1+t*inv(b)%p);
}
}
else{
b=(b+t*(a-1)%p)*inv(b+x1*(a-1)%p)%p;
printf("%lld\n",BSGS(a,b));
}
}
return 0;
}