总结 BSGS

求解关于 x 的 \(a^x\equiv b\pmod p\) 同余方程的算法。

用途

用于求这样的问题：

给出 \(a, b, p\) \[ a^x\equiv b\pmod p \] 求 \(x\) 的最小非负整数解

例题 Luogu P2485

思想

先把 \(x\) 拆分成 \(i*t-j\) 的形式（\(t=\lceil\sqrt{p}\rceil\)） \[ a^{i*t-j}\equiv b\pmod p\\ a^{i*t}\equiv b*a^j\pmod p \] 枚举 \(j\in [0,t]\) ，将 \(b*a^j\) 放进哈希表（我这么懒肯定用 \(map\) 水）

再枚举 \(i\in [0,t]\) ，从哈希表中查找 \(a^{i\ast t}\) ，找到即答案为 \(i\ast t-j\)

枚举 \(i,j\) 都是 \(O(\sqrt{p})\) 的

是不是很 easy

code

这里只好放 P2485 的代码了

map<LL, LL> m;
inline LL BSGS(int a, int b, int p) {
    m.clear();
    b %= p;
    if (a % p == 0) {// 恶心的特判
        if (b == 0) return 1;
        else return -1;
    }
    LL t = ceil(sqrt(p));
    for (LL i = 0, bn = b; i <= t; ++i)
        m[bn] = i, bn = bn * a % p;
    a = power(a, t);
    for (LL i = 0, an = 1, j; i <= t; ++i) {
        if (m.count(an)) {
            j = m[an];
            if (i * t - j >= 0)
                return i * t - j;
        }
        an = an * a % p;
    }
    return -1;
}

---

对于 p 不为质数的情况，我们需要 exBSGS 算法 求解。