P3846 [TJOI2007] 可爱的质数/【模板】BSGS

1
2
3
4
5
6
7
8
9
10
11
12
unordered_map<int, int> mp;
int Bsgs(int a, int b, int p) {
    if (1 % p == b % p) return 0;
    int k = sqrt(p) + 1;
    for (int i = 0, val = b % p; i < k; ++i, val = val * a % p) {
        mp[val] = i;
    }
    for (int i = 1, ak = power(a, k, p), val = ak; i <= k; ++i, val = val * ak % p) {
        if (mp.count(val)) return k * i - mp[val];
    }
    return -1;
}

Luogu P4195 【模板】扩展 BSGS/exBSGS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int exgcd(int a, int b, int &x, int &y) { /* ... */ }
inline int inv(int a, int p) { /* ... */ }

unordered_map<int, int> mp;
inline int Bsgs(int a, int b, int p) { /* ... */ }
int exBsgs(int a, int b, int p) {
    b = (b % p + p) % p;
    int d = gcd(a, p);
    if (d == 1) {
        return Bsgs(a, b, p);
    } else {
        if (1 % p == b % p) return 0;
        if (b % d) return NINF;
        else return exBsgs(a, b / d * inv(a / d, p / d), p / d) + 1;
    }
}