「学习笔记」模运算与 BSGS 算法

取模

取模符号：\(x \bmod y\)，表示 \(x\) 除以 \(y\) 得到的余数。

例如，

\[5 \bmod 3 = 2\\
7 \bmod 4 = 3\\
3 \bmod 3 = 0\\
\]

设 \(x\) 为被除数，\(y\) 为除数，\(z\) 为余数，则 \(x = k \cdot y + z, k = \lfloor \dfrac{x}{y} \rfloor\)。

模运算

\[\left (a + b \right ) \bmod c = \left (a \bmod c + b \bmod c \right ) \bmod c\\
\left (a - b \right ) \bmod c = \left (a \bmod c - b \bmod c \right ) \bmod c\\
\left (a \cdot b \right ) \bmod c = \left [\left (a \bmod c \right ) \cdot \left (b \bmod c \right ) \right ] \bmod c\\
\]

读入两个数 \(n, p\)，现在求 \((n!) \bmod p\) 是多少？\((2 < p \le 10^9, 1 \le n \le 1000)\)

\(\left ( n! \right ) \bmod p = \left [ \left ( n - 1 \right )! \bmod p \times n \bmod p \right] \bmod p\)

#include <iostream>

using namespace std;

int n, p;

int main() {

    cin >> n >> p;

    int ans = 1;

    for (int i = 1; i <= n; ++ i) {

        ans = 1ll * ans * i % p;

    }

    cout << ans << endl;

    return 0;

}

BSGS 算法

名称有很多，什么北上广深啊，等等，学名叫 baby-step giant-step，即大步小布算法。

我们由一个问题引入

给定三个数 \(a, b, p\)，\(p\) 是质数，解方程 \(a^x \bmod p = b\)。\((a, b, p \le 10^9)\)

暴力的做法

int solve(int a, int b, int p) {

// O(p)

    int v = 1;

    for (int x = 0; x <= p - 2; ++ x) {

        if (v == b)    return x;

        v = 1ll * v * a % p;

    }

    return -1;

}

由 \(a^{p - 1} \bmod p = 1\) 可知，余数会在 \(1\) 处循环。

\[a^{p - 1 + k} \bmod p\\
\begin{aligned}
&= a^{p - 1} \cdot a^k \bmod p\\
&= a^k \bmod p
\end{aligned}
\]

对于该方程，要枚举 \(p - 1\) 个数，那我们将这 \(p - 1\) 个数分组，\(s\) 为每组的大小。

\[a_0 \quad a_1 \quad a_2 \cdots \quad a^{s - 1}\\
\Downarrow (\cdot a^s) \Uparrow (\div a^s)\\
a^s \quad a^{s + 1} \quad a^{s + 2} \cdots a^{2s - 1}\\
a^2s \quad a^{2s + 1} \quad a^{2s + 2} \cdots a^{3s - 1}\\
\]

若第 \(2\) 组数中出现了 \(b\)，那么在第 \(1\) 组中，一定出现了 \(b \cdot a^{-s}\)。

#include <set>

using namespace std;

int solve(int a, int b, int p) {

    int s = sqrt(p);

    int v = 1;

    set<int> se;

    for (int i = 0; i < s; ++ i) {

        se.insert(v);

        v = 1ll * v * a % p;

    }

    // O(p / s)

    for (int i = 0; i * s <= p; ++ i) { // 看答案是否在第 i 行里面

        // 要看 b * a (-is) 是否在第 0 行出现

        int c = 1ll * b * qpow(qpow(a, i * s, p), p - 2, p) % p;

        if (se.count(c) != 0) {

            int v = qpow(a, i * s, p); // 第 i 行的第一个数

            for (int j = i * s; ; ++ j) { // O(s)

                if (v == b)    return j;

                v = 1ll * v * a % p;

            }

        }

    }

    return -1;

}

复杂度为：\(O(\dfrac{p}{s} + s) = O(\max(\dfrac{p}{s}, s))\)

若取 \(s = \sqrt{p}\)，则为 \(O_{\sqrt{p}}\)。