Skip to content

模运算

当我们在算法竞赛中看一些 \(\text{counting}\) 相关的题目时， 我们经常能看到：

  • 答案对 \(10^9 + 7\) 取模
  • 方案数对 \(998244353\) 取模

在我们刚接触算法竞赛的时候，我们总是会想「这个好办，直接对着答案 \(\% mod\) 不就行了吗。」

虽然从结果上来看，似乎确实是这样，但是其涉及到的模运算是算法竞赛非常重要的一部分， 不仅是在我们做数数题的时候取个模，还有很多基于模运算拓展出来的东西。

模与同余

给定一个 \(m\)，我们说 \(a\) 和 \(b\) 在模 \(m\) 的意义下「同余」，记作：

\[ a \equiv b \pmod m \]

定义：

\(a \equiv b \pmod m \Leftrightarrow m \mid (a-b)\)

也就是说：\(a\) 和 \(b\) 的差是 \(m\) 的倍数。 还有一种常见的等价写法：\(a = b + km,\ k \in \mathbb{Z}\)

举几个例子：

  • \(17 \equiv 5 \pmod{12}\)，因为 \(17-5=12\)
  • \(-1 \equiv 10 \pmod{11}\)，因为 \(-1-10=-11\)

直觉理解：

我们把整数的数轴按照 \(m\) 的步长进行折叠， 每隔 \(m\) 个数字就会重合在一起， 重合在一起的整数就是一个「同余系」。

也就是说在同余系中，我们不关心具体的数字，我们只关心模 \(m\) 的余数。

同余的关系满足三个性质：

  • 自反性：\(a \equiv a \pmod m\)
  • 对称性：\(a \equiv b \pmod m \Rightarrow b \equiv a \pmod m\)
  • 传递性：\(a \equiv b, b \equiv c \pmod m \Rightarrow a \equiv c \pmod m\)

所以我们可以把整数按这个关系分成若干类： 每一类对应一个余数 \(0,1,\dots,m-1\)。

这 \(m\) 个类组成的集合记作 \(\mathbb{Z}/m\mathbb{Z}\)，你可以理解为“模 \(m\) 的整数集合”。

模意义下的运算

假设存在：

\[ a \equiv b \pmod m , \ c \equiv d \pmod m \]

那么：

  • 加法：\(a + c \equiv b + d \pmod m\)
  • 减法：\(a - c \equiv b - d \pmod m\)
  • 乘法：\(ac \equiv bd \pmod m\)

这些的证明还是比较平凡的，例如对于加法：

\[ a - b = km, \ c - d = lm \rightarrow (a+c) - (b+d) = (k + l)m \]

这也就是为什么代码里我们会写： 

c = (a + b) % mod;
c = (a - b) % mod;
c = (1LL * a * b) % mod;
就是每一次运算之后，我们都加一个 \(\% mod\) 就可以了。 不过要注意减法产生负数的问题，我们接下来就会提到。

负数取模

数学上我们通常约定：余数在 \([0, m-1]\) 范围内。 但在 \(\text{C++}\) 中：

cout << (-1) % 5; // 会输出 -1，而不是输出 4

也就是说，当我们在 \(\text{C++}\) 中，我们进行取模的运算时， 余数会保持和左边的数字同号，左边的数字是正的，答案就是正的；是负的答案就是负的。

这就是为什么我们经常会在部分人的代码中看到： 

long long mod_norm(long long x, long long MOD){
    x %= MOD;
    if (x < 0) x += MOD;
    return x;
}
当然也有不开函数的「古法取模」： 
x = (x % MOD + MOD) % MOD;

日志

本页面创建于 2025/12/09 15:24