模运算的基本性质

模运算，又称同余运算，是数论中的一个重要概念。它描述了整数除以一个正整数（模数）后所得的余数。理解模运算的基本性质对于解决许多算法问题至关重要。以下是同余关系的一些核心性质：

• 定义： 若整数 a 和 b 在除以正整数 m 时具有相同的余数，则称 a 与 b 模 m 同余，记作 a \equiv b \pmod m。等价地，这意味着 m 整除 (a - b)。
• 加法性质： 若 a \equiv b \pmod m 且 c \equiv d \pmod m，则 (a + c) \equiv (b + d) \pmod m。
• 减法性质： 若 a \equiv b \pmod m 且 c \equiv d \pmod m，则 (a - c) \equiv (b - d) \pmod m。
• 乘法性质： 若 a \equiv b \pmod m 且 c \equiv d \pmod m，则 (a \times c) \equiv (b \times d) \pmod m。
• 指数性质： 若 a \equiv b \pmod m，则对于任意非负整数 n，有 a^n \equiv b^n \pmod m。
• 多项式性质： 若 a \equiv b \pmod m，则对于任意整系数多项式 P(x)，有 P(a) \equiv P(b) \pmod m。
• 模数约简： 若 a \equiv b \pmod m 且 d 是 m 的一个正因子，则 a \equiv b \pmod d。
  • 例如：320 \equiv 20 \pmod{100}。由于 50 是 100 的因子，所以 320 \equiv 20 \pmod{50}。
• 最大公约数性质： 若 a \equiv b \pmod m，则 \gcd(a, m) = \gcd(b, m)。
  • 例如：17 \equiv 2 \pmod 5。则 \gcd(17, 5) = 1 且 \gcd(2, 5) = 1。
• 模数和除数： 若 ac \equiv bc \pmod m 且 \gcd(c, m) = d，则 a \equiv b \pmod{m/d}。
  • 例如：320 \equiv 20 \pmod{100}，等价于 16 \times 20 \equiv 1 \times 20 \pmod{100}。由于 \gcd(20, 100) = 20，则 16 \equiv 1 \pmod{100/20}，即 16 \equiv 1 \pmod 5。
• 模运算的结合律：
  • (a + b) \pmod m = ((a \pmod m) + (b \pmod m)) \pmod m
  • (a \times b) \pmod m = ((a \pmod m) \times (b \pmod m)) \pmod m
  • a^n \pmod m = (a \pmod m)^n \pmod m

---

例题一：寻找最小模数 (POJ 2769 / PKU 2769 变种)

问题描述

给定 N 个整数，p_0, p_1, ..., p_{N-1}。目标是找到最小的正整数 K，使得这 N 个整数除以 K 所得的余数互不相同。

分析与优化

如果存在两个整数 p_i 和 p_j（i \neq j），使得 p_i \equiv p_j \pmod K，那么 K 就不是我们寻找的答案。这等价于 K 整除 (p_i - p_j)。也就是说，如果 K 是任意两个输入数字之差的绝对值 |p_i - p_j| 的因子，那么这 N 个数字中至少有两个在模 K 意义下同余。

更进一步地，如果 K = |p_i - p_j| 对于某个 i, j 成立，那么 p_i \equiv p_j \pmod K 必然成立（因为 p_i - p_j = \pm K）。在这种情况下，p_i 和 p_j 模 K 的余数相同（都为 p_j \pmod K 或 p_i \pmod K），因此 K 不能作为答案。

这一观察提供了一个重要的优化策略：我们只需要检查那些不等于任意 |p_i - p_j| 的正整数 K。因为如果 K 是某个 |p_i - p_j| 的值，那么它一定不满足条件。这个"剪枝"操作可以显著减少需要检查的 K 的数量。

示例代码

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <cstring> // For memset

const int MAX_VAL = 1000010; // 假设数字和K的范围

int input_numbers[330];
bool remainder_seen[MAX_VAL]; // 检查当前K下余数是否重复
bool is_abs_diff[MAX_VAL];   // 标记是否为任意两个输入数字的绝对差

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int test_cases;
    std::cin >> test_cases;
    while (test_cases--) {
        int count;
        std::cin >> count;
        for (int i = 0; i < count; ++i) {
            std::cin >> input_numbers[i];
        }

        // 优化：预处理所有绝对差值
        // 如果 K 是某个 |p_i - p_j|，则 p_i % K == p_j % K，K 不可能成为答案。
        // 所以我们只检查那些不是任何绝对差值的 K。
        memset(is_abs_diff, 0, sizeof(is_abs_diff)); // 重置标记数组
        for (int i = 0; i < count; ++i) {
            for (int j = 0; j < count; ++j) {
                if (i == j) continue;
                int diff = std::abs(input_numbers[i] - input_numbers[j]);
                if (diff < MAX_VAL) { // 确保索引不越界
                    is_abs_diff[diff] = true;
                }
            }
        }

        // 遍历 K 寻找最小解
        for (int k = 1; ; ++k) {
            if (k >= MAX_VAL) { // K超过预设最大值，理论上不会发生，作为安全退出
                break;
            }

            // 如果 k 是某个绝对差值，则跳过
            if (is_abs_diff[k]) {
                continue;
            }

            // 检查当前 K 是否满足所有数字余数互不相同
            memset(remainder_seen, 0, sizeof(remainder_seen)); // 重置余数标记
            bool all_remainders_distinct = true;
            for (int i = 0; i < count; ++i) {
                int remainder = input_numbers[i] % k;
                if (remainder_seen[remainder]) {
                    all_remainders_distinct = false; // 发现重复余数
                    break;
                }
                remainder_seen[remainder] = true;
            }

            if (all_remainders_distinct) {
                std::cout << k << "\n";
                break; // 找到最小 K，退出
            }
        }
    }
    return 0;
}

---

例题二：斐波那契数列模运算 (HDU 1021)

问题描述

定义一个特殊的斐波那契数列：F_0 = 7, F_1 = 11，且 F_n = F_{n-1} + F_{n-2}（对于 n \ge 2）。给定一个整数 n，判断 F_n 是否能被 3 整除。

分析与Pisano周期

要判断 F_n 是否能被 3 整除，我们只需要计算 F_n \pmod 3 的值。斐波那契数列对某个模数 m 取余时，会呈现周期性，这个周期被称为 Pisano 周期。

我们来推导这个数列模 3 的情况：

• F_0 = 7 \equiv 1 \pmod 3
• F_1 = 11 \equiv 2 \pmod 3
• F_2 \equiv (F_1 + F_0) \pmod 3 \equiv (2 + 1) \pmod 3 \equiv 0 \pmod 3
• F_3 \equiv (F_2 + F_1) \pmod 3 \equiv (0 + 2) \pmod 3 \equiv 2 \pmod 3
• F_4 \equiv (F_3 + F_2) \pmod 3 \equiv (2 + 0) \pmod 3 \equiv 2 \pmod 3
• F_5 \equiv (F_4 + F_3) \pmod 3 \equiv (2 + 2) \pmod 3 \equiv 1 \pmod 3
• F_6 \equiv (F_5 + F_4) \pmod 3 \equiv (1 + 2) \pmod 3 \equiv 0 \pmod 3
• F_7 \equiv (F_6 + F_5) \pmod 3 \equiv (0 + 1) \pmod 3 \equiv 1 \pmod 3
• F_8 \equiv (F_7 + F_6) \pmod 3 \equiv (1 + 0) \pmod 3 \equiv 1 \pmod 3

观察 (F_n \pmod 3, F_{n+1} \pmod 3) 的对序列：(1,2) \to (2,0) \to (0,2) \to (2,2) \to (2,1) \to (1,0) \to (0,1) \to (1,1) \to (1,2)。 可以发现，这个序列从 (F_0, F_1) 到 (F_8, F_9) 经历了 8 对，第九对 (F_8, F_9) 即为 (1,2)，与 (F_0, F_1) 相同，因此序列以 8 为周期重复。 这意味着 F_n \pmod 3 的值只取决于 n \pmod 8 的值。数列的模 3 结果为 1, 2, 0, 2, 2, 1, 0, 1 循环。

因此，当 n \pmod 8 的结果为 2 或 6 时，F_n \pmod 3 = 0，即 F_n 可以被 3 整除。

为了处理大量查询，可以预先计算出足够大的 F_n \pmod 3 值并存储在一个数组中。

示例代码

#include <iostream>
#include <vector> // 使用vector代替C风格数组，更现代且灵活
#include <cstring> // For memset, if using C-style array

const int MAX_N = 1000000;
std::vector<int> fib_mod_3_values(MAX_N + 1); // 存储 F_n % 3 的值

void precompute_fibonacci_mod_3() {
    // 初始值
    fib_mod_3_values[0] = 7 % 3;  // F_0 = 1
    fib_mod_3_values[1] = 11 % 3; // F_1 = 2

    // 根据递推关系计算后续项的模 3 值
    for (int i = 2; i <= MAX_N; ++i) {
        fib_mod_3_values[i] = (fib_mod_3_values[i-1] + fib_mod_3_values[i-2]) % 3;
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    precompute_fibonacci_mod_3(); // 预处理

    int n;
    while (std::cin >> n) {
        if (n < 0 || n > MAX_N) {
            // 处理超出预计算范围的 n，这里简化为示例，实际应根据问题要求处理
            std::cout << "Error: n out of range" << "\n";
            continue;
        }

        if (fib_mod_3_values[n] == 0) {
            std::cout << "yes" << "\n";
        } else {
            std::cout << "no" << "\n";
        }
    }
    return 0;
}

---

例题三：快速幂取模 (HDU 2035)

问题描述

计算 A^B \pmod{1000} 的值，其中 A 和 B 是整数。

分析与快速幂算法

直接计算 A^B 然后再取模对于很大的 B 是不可行的，因为 A^B 会迅速超出标准数据类型的表示范围，并且循环 B 次的朴素乘法方法时间复杂度太高（O(B)）。我们需要一种更高效的算法，即快速幂（或称二进制取幂）。

快速幂算法利用了指数的二进制表示。例如，要计算 A^B，我们可以将 B 写成二进制形式：B = b_k 2^k + b_{k-1} 2^{k-1} + \dots + b_1 2^1 + b_0 2^0。 那么 A^B = A^{(b_k 2^k + \dots + b_0 2^0)} = A^{b_k 2^k} \times \dots \times A^{b_0 2^0}。 其中 A^{2^j} 可以通过重复平方得到：A^{2^0} = A，A^{2^1} = (A^{2^0})^2，A^{2^2} = (A^{2^1})^2，依此类推。

在计算 A^B \pmod M 时，我们在每一步乘法后都取模，以防止中间结果溢出。

算法步骤：

1. 初始化结果 res = 1。
2. 将底数 A 对模数 M 取模：A = A \pmod M。
3. 当指数 B > 0 时循环：
   • 如果 B 是奇数（即 B 的二进制最低位为 1），则将 res 乘以 A 并对 M 取模：res = (res \times A) \pmod M。
   • 将 A 自乘并对 M 取模：A = (A \times A) \pmod M。（这相当于计算 A^{2^1}, A^{2^2}, A^{2^3}, \dots）
   • 将 B 右移一位（即 B = B / 2）。
4. 循环结束后，res 即为 A^B \pmod M 的结果。

快速幂的时间复杂度为 O(\log B)。

示例代码

#include <iostream>

// 快速幂取模函数
// 计算 (base ^ exponent) % modulus
int power_modulo(int base, int exponent, int modulus) {
    long long result = 1; // 使用 long long 防止中间乘法溢出，即使 modulus 较小
    long long current_base = base % modulus; // 确保底数在模数范围内

    while (exponent > 0) {
        // 如果 exponent 的当前位是 1 (即 exponent 为奇数)
        if (exponent % 2 == 1) {
            result = (result * current_base) % modulus;
        }
        // base 自乘，相当于计算 base^2, base^4, base^8...
        current_base = (current_base * current_base) % modulus;
        // exponent 右移一位，相当于除以 2
        exponent /= 2;
    }
    return static_cast<int>(result);
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int a, b;
    // 循环读取输入，直到 A 为 0 结束
    while (std::cin >> a >> b && (a != 0 || b != 0)) {
        // A=0, B=0 的情况通常需要特殊处理，比如定义为1或不合法
        // 根据题目要求，如果 A=0 B=0 循环停止，所以这里不会处理。
        // 一般来说 0^0=1
        if (a == 0 && b == 0) {
            // 根据题目结束条件，A=0 B=0是输入结束标志
            // 实际计算可能需要定义 0^0 = 1
            // 但此题的循环条件已经处理了，所以这里不需额外输出
            break;
        }
        
        // 计算 A^B % 1000
        int ans = power_modulo(a, b, 1000);
        
        // 由于结果可能不足三位，题目通常要求输出三位
        // 例如，2^3 % 1000 = 8，输出 008
        // std::printf("%03d\n", ans);
        // 但题目只要求输出结果，不一定要求格式，因此直接输出
        std::cout << ans << "\n";
    }

    return 0;
}