BZOJ3122 [SDOI2013 随机数生成器]

传送门

题目大意

给定参数$a,b,X_1,p$,我们以下列方式生成一个序列:
$$
X_{i+1}=(aX_i+b)%p
$$
其中$p$是质数。

询问$t$第一次出现的位置,如果永远不出现输出$-1$。

解析

考虑展开这个式子。

我们得到:
$$
\begin{align*}
t&=x_i\\
&\equiv ax_{i-1}+b\\
&\equiv a(ax_{i-2}+b)+b\\
&\equiv a(a(ax_{i-3}+b)+b)+b\\
&\equiv …\\
&\equiv a^{i-1}(x_1+\frac b{a-1})-\frac b{a-1}
\end{align*}
$$
然后大力$BSGS$一下就可以了。

小细节特判一下。

Code(modify from hzwer)

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
93
94
95
96
97
98
99
#define  REP(i, s, e) for (int i = s; i <= e; i++)
#define DREP(i, s, e) for (int i = s; i >= e; i--)
#define DEBUG fprintf(stderr, "Passing [%s] in Line %d\n", __FUNCTION__, __LINE__)

#define chkmax(a, b) a = max(a, b)
#define chkmin(a, b) a = min(a, b)

#include <iostream>
#include <cstdio>
#include <cmath>
#include <tr1/unordered_map>
#define int long long

using namespace std;

int p, a, b, x1, t;

int exgcd(int a, int b, int &x, int &y)
{
if (!b)
{
x = 1;
y = 0;
return a;
}
int res = exgcd(b, a % b, y, x);
y -= a / b * x;
return res;
}

inline int power_pow(int base, int b, int MOD)
{
base %= MOD;
int ans(1);
while (b)
{
if (b & 1) ans = ans * base % MOD;
base = base * base % MOD;
b >>= 1;
}
return (ans + MOD) % MOD;
}
tr1::unordered_map <int, int> mp;
inline int bsgs(int A, int B, int C)
{
A %= C;
if(!A) return B ? -1 : 1;
int m=sqrt(C) + 1, t = 1, I = 1, Im = power_pow(A, C-1-m, C);
mp.clear();mp[1]=m+1;
REP(i, 1, m - 1)
{
t = t * A % C;
if (!mp[t]) mp[t]=i;
}
REP(k, 0, m - 1)
{
int i = mp[B * I % C];
if (i)
{
if (i == m + 1) i = 0;
return k * m + i;
}
I = I * Im % C;
}
return -1;
}
inline int cal1()
{
int C = (t - x1 + p) % p, x, y;
int t = exgcd(b, p, x, y);
if (C % t) return -1;
x = x * (C /= t) %p;
if (x < 0) x += p;
return x+1;
}
inline int cal2()
{
int c = power_pow(a - 1, p - 2, p), A = (x1 + b * c) % p, C = (t + b * c) % p, x, y;
int t = exgcd(A, p, x, y);
if (C % t) return -1;
C /= t;
if (x < p) x = x % p + p;
t = bsgs(a, x * C % p, p);
return t == -1 ? -1 : t + 1;
}
signed main()
{
#ifdef CraZYali
freopen("3122.in", "r", stdin);
freopen("3122.out", "w", stdout);
#endif
int Case;cin >> Case;
while (Case--)
{
scanf("%lld%lld%lld%lld%lld", &p, &a, &b, &x1, &t);
printf("%lld\n", x1 == t ? 1 : a == 0 ? b == t ? 2 : -1 : a == 1 ? cal1() : cal2());
}
return 0;
}
# 数论

评论

Your browser is out-of-date!

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

×