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

取模

取模符号:(x mod y),表示 (x) 除以 (y) 得到的余数。

例如,

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

(x) 为被除数,(y) 为除数,(z) 为余数,则 (x = k cdot y + z, k = lfloor dfrac{x}{y} floor)

模运算

[left (a + b ight ) mod c = left (a mod c + b mod c ight ) mod c\ left (a - b ight ) mod c = left (a mod c - b mod c ight ) mod c\ left (a cdot b ight ) mod c = left [left (a mod c ight ) cdot left (b mod c ight ) ight ] mod c\ ]

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

(left ( n! ight ) mod p = left [ left ( n - 1 ight )! mod p imes n mod p ight] mod 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 mod 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} mod p = 1) 可知,余数会在 (1) 处循环。

[a^{p - 1 + k} mod p\ egin{aligned} &= a^{p - 1} cdot a^k mod p\ &= a^k mod 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}})

原文地址:https://www.cnblogs.com/yifan0305/p/17454589.html