模算术基础

1. 整除

若存在整数 k，使得 b = k × a，则称 a 能整除 b，记作 a | b，此时 a 是 b 的约数。

性质： 如果 a | b 且 a | c，那么对于任意整数 m 和 n，a 也整除 ma + nb。

2. 同余

如果 a 和 b 除以 m 的余数相同，则称 a 与 b 模 m 同余，记作 a ≡ b (mod m)，这等价于 m 能整除 (a - b)。

性质：

• 加减法： 若 a ≡ x (mod m) 且 b ≡ y (mod m)，则 a ± b ≡ x ± y (mod m)。
• 乘法： 若 a ≡ x (mod m) 且 b ≡ y (mod m)，则 ab ≡ xy (mod m)。若 a ≡ b (mod m)，则 a^k ≡ b^k (mod m)。
• 除法：
  • 若 ac ≡ bc (mod m) 且 c 与 m 互质，则 a ≡ b (mod m)。
  • 若 a ≡ b (mod m) 且 d 是 a, b, m 的公约数，则 a/d ≡ b/d (mod m/d)。
• 模运算的结合律：
  • (a ± b) % m = ((a % m) ± (b % m)) % m
  • (a × b) % m = ((a % m) × (b % m)) % m
• 乘法逆元： 当 a 与 m 互质时，存在一个整数 inv_a，使得 a × inv_a ≡ 1 (mod m)。inv_a 称为 a 模 m 的乘法逆元。

求法：

• 费马小定理： 当 m 为质数时，inv_a = a^m-2 (mod m)。
• 扩展欧几里得算法： 通过求解 ax + my = 1 来找到 x，即为逆元。

素数

1. 算术基本定理

任何大于 1 的整数都可以唯一地表示为若干个素数的幂的乘积，即 n = p₁^α₁ × p₂^α₂ × ... × p_k^αₖ。

推论：

• 约数个数：∏(α_i + 1)
• 约数和：∏(1 + p_i + p_i² + ... + p_i^αᵢ) = ∏(p_i^αᵢ+1 - 1) / (p_i - 1)
• 最大公约数与最小公倍数：(a, b) = ∏p_i^{min(αᵢ, βᵢ)}，[a, b] = ∏p_i^{max(αᵢ, βᵢ)}，且 (a, b) × [a, b] = a × b。

2. 素数判定

2.1 埃拉托斯特尼筛法

对于每个找到的素数，标记其所有倍数为合数。

for (int i = 2; i <= n; ++i) {
    if (is_prime[i]) {
        prime_list.push_back(i);
        for (int j = i * i; j <= n; j += i) {
            is_prime[j] = false;
        }
    }
}

2.2 欧拉筛法

确保每个合数只被其最小的质因子筛掉一次，时间复杂度为 O(n)。

for (int i = 2; i <= n; ++i) {
    if (is_prime[i]) {
        prime_list.push_back(i);
    }
    for (int j = 0; j < prime_list.size() && i * prime_list[j] <= n; ++j) {
        is_prime[i * prime_list[j]] = false;
        if (i % prime_list[j] == 0) {
            break;
        }
    }
}

2.3 Miller-Rabin 素性测试

一种概率性算法，通过多次测试来高概率地判断一个数是否为素数。

bool is_prime(long long n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0) return false;

    // 将 n-1 分解为 d * 2^s
    long long d = n - 1;
    int s = 0;
    while (d % 2 == 0) {
        d /= 2;
        ++s;
    }

    // 进行 k 次测试
    for (int i = 0; i < k; ++i) {
        long long a = random_number(2, n - 2);
        long long x = fast_pow(a, d, n);
        if (x == 1 || x == n - 1) continue;
        bool composite = true;
        for (int j = 0; j < s - 1; ++j) {
            x = (x * x) % n;
            if (x == n - 1) {
                composite = false;
                break;
            }
        }
        if (composite) return false;
    }
    return true;
}

核心定理与算法

1. 欧几里得算法

用于计算两个整数的最大公约数 (GCD)。

原理： gcd(a, b) = gcd(b, a % b)。由于每次迭代中较大的数至少减半，因此时间复杂度为 O(log(min(a, b)))。

2. 扩展欧几里得算法

不仅计算 GCD，还能找到整数 x 和 y，使得 ax + by = gcd(a, b)。

应用： 用于求解形如 ax ≡ 1 (mod m) 的乘法逆元（当 a 和 m 互质时）。

3. 欧拉函数与欧拉定理

欧拉函数 φ(n)： 小于 n 且与 n 互质的正整数的个数。

性质： 若 a 和 b 互质，则 φ(ab) = φ(a) × φ(b)。

通式： φ(n) = n × ∏(1 - 1/p_i)，其中 p_i 是 n 的所有不同质因数。

欧拉定理： 若 a 与 m 互质，则 a^φ(m) ≡ 1 (mod m)。

4. 中国剩余定理 (CRT)

用于求解一组同余方程组，其中模数两两互质。

给定方程组 x ≡ a_i (mod m_i)，其中 m_i 互质，求解 x。

解法： 令 M = ∏m_i，M_i = M / m_i。找到 M_i 模 m_i 的逆元 y_i。则 x = Σ(a_i × M_i × y_i) 是一个解。

5. 卢卡斯定理

用于计算大组合数对质数取模的结果。

定理：C(n, k) % p = [C(n/p, k/p) × C(n%p, k%p)] % p