Luogu P3306 [SDOI2013] 随机数生成器

qwq

数列神题(

$x_{i+1} = (ax_i + b) \mod p$,使用构造法,$x_{i + 1} + \lambda = a(x_i + \lambda) \mod p$.

解得:$\lambda = \frac{b}{a - 1}$.

则数列${x_i}$通项公式为$x_i = (x_1 + \frac{b}{a - 1}) a^{i - 1}$.

当$x_i = t$时,$(x_1 + \frac{b}{a - 1}) a^{i - 1} = t$,即:$a_{i - 1} \equiv t \times (x_1 + \frac{b}{a - 1}) ^ {-1} \mod p$.

这是BSGS的形式,根据这玩意解就完事了。

关于BSGS 拔山盖世,它用于求解 $a^x \equiv b \mod p$ 这样的同余方程。

主要思路:把 $x$ 拆成 $i m - j$, $a^{i m} \equiv b * a ^ {j} \mod p$.

从0 - m 枚举j算出右式的值塞到Hash Table,由于拆成减的形式,j越大越优。

最后枚举i,求左式,在Hash Table找对应值,找到就是答案,最后找不到无解。

因为我很懒,天天用map

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
#include <bits/stdc++.h>

long long p, a, b, x_1, t, T, tt;

long long Qpow(long long x, long long y, long long p) {
long long ret = 1;
for (; y; y >>= 1, x = x * x % p)
if (y & 1) ret = ret * x % p;
return ret;
}

long long BSGS(long long x, long long y, long long p) {
long long m = ceil(sqrt(p)), t = 1;
std::map<long long, long long> hash;
for (int i = 0; i <= m; i++, y = y * x % p) hash[y] = i;
long long f = Qpow(a, m, p);
for (int i = 1; i <= m; i++) {
t = t * f % p;
if (hash.count(t)) return i * m - hash[t] + 1;
}
return -1;
}

signed main() {
scanf("%lld", &T);
while (T--) {
scanf("%lld%lld%lld%lld%lld", &p, &a, &b, &x_1, &t);
if (x_1 == t) {puts("1"); continue;}
if (a == 0) {puts(b == t ? "2" : "-1"); continue;}
if (a == 1) {
if (b == 0) {puts("-1"); continue;}
long long c = Qpow(b, p - 2, p) % p, d = (t - x_1 + p) % p;
printf("%lld\n", d * c % p + 1);
continue;
}
long long u = b * Qpow(a - 1, p - 2, p) % p;
tt = ((t + u) * Qpow((x_1 + u) % p, p - 2, p)) % p;
printf("%lld\n", BSGS(a, tt, p));
}
return 0;
}

评论

Your browser is out-of-date!

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

×