RenaMoe's Blog

念念不忘，必有回响

0%

总结 exBSGS

发表于 分类于 ， Valine：

求解 \(a^x\equiv b\pmod p\) 其中 p 不为质数情况的算法。

需要提前掌握 BSGS。

模板题：Luogu P4195。

思路

p 不为质数时，我们需要让 \(\gcd(a, p)=1\) 才能进行朴素 BSGS。

对于 \[ a^x\equiv b\pmod p \] 设 \(d=\gcd(a,p)\)， \[ a^{x-1}\times a\equiv b \pmod p\\ a^{x-1}\times \frac{a}{d}\equiv \frac{b}{d} \pmod{\frac{p}{d}}\\ a^{x-1}\equiv \frac{\frac{b}{d}}{\frac{a}{d}}\pmod{\frac{p}{d}} \] 若 \(\gcd(a^{x-1},\frac{p}{d})\neq 1\)，循环下去，直到 a,p 互质，进行朴素 BSGS 即可。

需要注意，若在过程中出现 \(d\not\mid b\) 即无解。

另外，如果循环第 k 次时 \[ a^{x-1}\equiv \frac{\frac{b}{d}}{\frac{a}{d}}\equiv 1\pmod{\frac{p}{d}} \] 此时 \(x-1=0\)，最后答案为 k。

实现

直接做的话，要求 \(\frac{a}{d}\) 在模 \(\frac{p}{d}\) 意义下的逆元，\(\frac{p}{d}\) 不为质数，需要 exgcd 求逆元。

不写 exgcd 实现的话，设 \(c=\frac{a}{d}\)，转化到 BSGS 中现在要求解 \(a^x\equiv \frac{b}{c}\pmod p\)，将 c 乘到左边后做。

所以只要把 \(\frac{a}{d}\) 传入 BSGS 就行。

exBSGS code

1
2
3
4
5
6
7
8
9
10
11
12
inline LL exBSGS(LL a, LL b, LL p) {
    a %= p, b %= p;
    if (b == 1 || p == 1) return 0; // 特判
    LL d, cnt = 0, ad = 1; // 分别是gcd(a,p)，循环次数，a/d
    while ((d = gcd(a, p)) > 1) {
        if (b % d) return -1;
        cnt++, b /= d, p /= d, ad = ad * a / d % p;
        if (ad == b) return cnt;
    }
    LL ans = BSGS(a, b, p, ad);
    return ans == -1 ? -1 : ans + cnt;
}

luogu P4195 code

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
#include <cstdio>
#include <cctype>
#include <unordered_map>
#include <cmath>
using namespace std;

namespace RenaMoe {
template<typename T> inline void read(T &x) {}

typedef long long LL;

unordered_map<LL, LL> mp;

inline LL power(LL a, LL b, LL p) {
    LL ans = 1;
    while (b) {
        if (b & 1) ans = ans * a % p;
        a = a * a % p, b >>= 1;
    }
    return ans;
}

inline LL BSGS(LL a, LL b, LL p, LL ad) {
    mp.clear();
    b %= p;
    if (a % p == 0) {
        if (b == 1) return 1;
        else return -1;
    }
    LL t = ceil(sqrt(p)), an = b;
    for (int i = 0; i <= t; ++i)
        mp[an] = i, an = an * a % p;
    a = power(a, t, p), an = ad;
    for (int i = 0, j; i <= t; ++i) {
        if (mp.count(an)) {
            j = mp[an];
            if (i * t - j >= 0) return i * t - j;
        }
        an = an * a % p;
    }
    return -1;
}

LL gcd(LL x, LL y) {
    return y ? gcd(y, x % y) : x;
}

inline LL exBSGS(LL a, LL b, LL p) {
    a %= p, b %= p;
    if (b == 1 || p == 1) return 0;
    LL d, cnt = 0, ad = 1;
    while ((d = gcd(a, p)) > 1) {
        if (b % d) return -1;
        cnt++, b /= d, p /= d, ad = ad * a / d % p;
        if (ad == b) return cnt;
    }
    LL ans = BSGS(a, b, p, ad);
    return ans == -1 ? -1 : ans + cnt;
}

inline void main() {
    LL a, p, b;
    while (1) {
        read(a), read(p), read(b);
        if (!a && !b && !p) break;
        LL ans = exBSGS(a, b, p);
        if (ans == -1) puts("No Solution");
        else printf("%lld\n", ans);
    }
}
}

int main() {
    RenaMoe::main();
    return 0;
}