「BZOJ-3122」[Sdoi2013]随机数生成器(BSGS)

发表于 | 分类于 ，

BZOJ3122-[Sdoi2013]随机数生成器
有递推式X(i+1)=(aX(i)+b) mod p， 求最小的i使X(i)=t

题解

$$X_i=aX_{i-1}+b$$

$$\ \quad=a^2X_{i-2}+ab+b​$$

$$=…$$

$$\ \quad=a^{i-1}X_{1}+a^{i-2}b+a^{i-1}b+…+ab+b​$$

$$\ \quad=a^{i-1}X_{1}+b{a^{i-1}-1 \over a-1}​$$

又$X_i=t$，有$$a^{i-1}X_1+b{a^{i-1}-1 \over a-1}≡t \ mod \ p$$

其中只有$a_{i-1}$为未知量，对其化简得

$$a^{i-1}≡{(a-1)t+b \over (a-1)x_1+b} \ mod \ p​$$

其中$i$为题目要我们求的答案。

首先特判几种情况：

①$a=0$时，原式为$X_i=b$，若$t=b$，则$i=1$；否则无解，输出-1；

②$a=1$时，若$b=0$，分式分母为0，无解，输出-1；否则原式为$X_i=X_1+(i-1)b$，对$i$化简有$i={t-x_1 \over b}+1$，逆元求解即可；

③$X_1=t$时，有$a^{i-1}=1$，此时易得$i=1​$；

如果不存在上述情况，对于式子

$$a^{i-1}≡{(a-1)t+b \over (a-1)x_1+b} \ mod \ p$$

两边同乘$a$，有式子$$a^i≡a{(a-1)t+b \over (a-1)x_1+b} \ mod \ p$$

BSGS即可求出$i$。

代码

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

using namespace std;

int qp(int a, int n, int mod)
{
    long long ans = 1, base = a % mod;
    while(n)
    {
        if(n & 1) (ans *= base) %= mod;
        (base *= base) %= mod;
        n >>= 1;
    }
    return ans;
}

int inv(int a, int p) { return qp(a, p - 2, p); }

int BSGS(int a, int b, int p)
{
    map<int, int> hash;
    b %= p;
    int t = (int)sqrt(p) + 1;
    for(int j =0; j < t; j ++)
    {
        int val = 1ll * b * qp(a, j, p) % p;
        hash[val] = j;
    }
    a = qp(a, t, p);
    if(a == 0) return b == 0 ? 1 : -1;
    for(int i = 1; i <= t; i ++)
    {
        int val = qp(a, i, p);
        int j = hash.find(val) == hash.end() ? -1 : hash[val];
        if(j >= 0 && i * t - j >= 0) return i * t - j;
    }
    return -1;
}

signed main()
{
    int _, p, a, b, x, t;
    scanf("%lld", &_);
    while(_ --)
    {
        scanf("%lld%lld%lld%lld%lld", &p, &a, &b, &x, &t);
        if(x == t) { puts("1"); continue; }
        if(a == 0) { printf("%d\n", t == b ? 2 : -1); continue; }
        else if(a == 1) {printf("%lld\n", b ? ((((t - x) % p + p) % p) * inv(b, p) % p + 1) : -1); continue; }
        int tmp = b * inv(a - 1, p) % p;
        int y = (t + tmp) % p * inv((x + tmp) % p, p) % p * a % p;
        int ans = BSGS(a, y, p);
        printf("%lld\n", ans);
    }
    return 0;
}