模运算基础

什么是模运算？

想象一下时钟。现在是10点，5个小时后是几点？你不会说是15点，而是会说是3点。你下意识地进行了一次计算： $(10 + 5) \div 12$ ，余数是3。这就是模运算的核心思想：我们只关心余数。

在数学和编程中，模运算无处不在。它帮助我们处理那些具有循环特性的问题，就像时钟一样。

模

noun

在模运算中，我们除以的那个数。在时钟的例子里，模是12。它定义了我们循环的范围。

同余关系

数学家们用一种特殊的方式来表达“两个数除以同一个数余数相同”这个概念，称之为“同余”。

a \equiv b \pmod{n}

在 C++ 编程中，我们通常使用百分号运算符（%）来获得余数。所以，要检查两个数 a 和 b 是否关于模 n 同余，你可以比较它们各自的取模结果。

// 检查 a 和 b 是否模 n 同余
if (a % n == b % n) {
  // 它们是同余的
}

处理负数

当你开始处理负数时，事情就变得有点棘手了。数学上的同余通常期望余数是非负的（即在 $0$ 到 $n-1$ 的范围内）。但是，C++（以及许多其他编程语言）在处理负数取模时，可能会返回一个负数结果。

#include <iostream>

int main() {
    // C++ 中负数取模的结果可能为负
    std::cout << -5 % 3 << std::endl; // 输出 -2，而不是 1
    return 0;
}

在算法竞赛或需要用取模结果作为数组索引时，一个负数索引会导致程序崩溃。为了解决这个问题，我们可以使用一个可靠的公式，确保结果始终在 $0$ 到 $n-1$ 的范围内。

修正负数取模的技巧是 (a % n + n) % n。

我们来分解一下这个公式：

a % n：首先进行标准的取模运算。如果 a 是正数，结果就是我们想要的。如果 a 是负数，我们可能会得到一个负数（如 -2）。
+ n：如果上一步的结果是负数，加上模 n 可以保证结果变为正数。例如，-2 + 3 = 1。如果上一步的结果已经是正数，加上 n 也没关系，因为下一步会修正它。
% n：最后再进行一次取模。这一步是为了处理上一步中 a 为正数的情况。例如，如果 a 是 5，n 是 3，那么 (5 % 3 + 3) % 3 变成了 (2 + 3) % 3，也就是 5 % 3，结果仍然是 2。

#include <iostream>

int main() {
    int a = -5;
    int n = 3;

    // 修正公式确保结果为非负数
    int remainder = (a % n + n) % n;

    std::cout << remainder << std::endl; // 输出 1
    return 0;
}

周期性的应用

模运算最强大的用途是处理周期性或循环性的数据。想象一个循环数组，当你到达最后一个元素的下一个位置时，你希望它能“绕回”到第一个元素。

假设你有一个包含 n 个元素的数组，索引从 0 到 n-1。如果你当前在索引 i，想移动到下一个元素，你可以用 (i + 1) % n 来计算下一个索引。如果 i 是 n-1，那么 (n - 1 + 1) % n 就是 n % n，结果是 0，正好回到了数组的开头。

这在很多场景中都很有用，比如处理星期几（模 7）、棋盘游戏或者任何需要循环逻辑的地方。

Quiz Questions 1/5

在C++中，对于一个包含 n 个元素（索引从 0 到 n-1）的数组，如何安全地计算当前索引 i 向前移动一位（循环到数组末尾）的索引？

Quiz Questions 2/5

在C++中，代码 (-5 % 3) 的计算结果是什么？

掌握模运算，尤其是如何正确处理负数，是许多算法的基础。它能让你写出更简洁、更安全的代码来处理循环数据。

从零开始掌握模运算算法