BZOJ3122 [SDOI2013] 随机数生成器

传送门

已知 $a,b,X_1,p,t$ ,

给定递推公式 $X_{i+1}=(aX{i}+b)\mod p(i\ge 1)$ ,求最小的正整数i满足 $X_i=t$ ,p为质数。

题解

这道题需要分类讨论:

  1. 当$X_1=t$时,答案为1.
  2. 当a=0时,如果b=t,则答案为2,否则无解。
  3. 当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即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
/*
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;
}

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×