模运算

✨ 什么是模运算？¶

模运算（Modular Arithmetic） 是指对一个数取余的运算，用于控制数值范围、防止溢出，是信息学竞赛中常见的技巧。

记号：

\[ a \bmod m = r \]

表示当 $a$ 除以 $m$ 的余数为 $r$。

例如：

\[ 17 \bmod 5 = 2 \]

🧩 模运算的基本性质¶

我们设模数为 $m$，则模运算具有如下代数性质：

1. 自反性（同余关系）¶

若 $a \equiv b \pmod{m}$，则 $b\equiv a \pmod{m}$。

示例：

\[ 17 \equiv 2 \pmod{5} \Longrightarrow 2 \equiv 17 \pmod{5} \]

2. 可加性（加法保同余）¶

若 $a \equiv b \pmod{m}$，则对任意整数 $c$，都有：

\[ a + c \equiv b + c \pmod{m} \]

换句话说，模数下同余的两个数，加上相同的数，结果仍然同余。

从运算角度，也有：

\[ (a + b) \bmod m = (a \bmod m + b \bmod m) \bmod m \]

3. 可减性（减法保同余）¶

若 $a \equiv b \pmod{m}$，则：

\[ a - c \equiv b - c \pmod{m} \]

计算时：

\[ (a - b) \bmod m = ((a \bmod m - b \bmod m) + m) \bmod m \]

（加 $m$ 是为了避免负数）

4. 可乘性（乘法保同余）¶

若 $a \equiv b \pmod{m}$，则：

\[ a \times c \equiv b \times c \pmod{m} \]

换句话说：

\[ (a \times b) \bmod m = (a \bmod m \times b \bmod m) \bmod m \]

5. 结合律与交换律¶

模运算下的加法与乘法满足交换律与结合律：

\[\begin{aligned} &(a + b) \bmod m \equiv (b + a) \bmod m\\ &(a \times b) \bmod m \equiv (b \times a) \bmod m\\ &c \times (a + b) \bmod m \equiv (c \times a + c \times b)\bmod m\equiv (c \times a \bmod m+ c \times b\bmod m)\bmod m \end{aligned}\]

⚠️ 除法不可直接模¶

一般情况：

\[ (a / b) \bmod m \ne (a \bmod m) / (b \bmod m) \]

除法的模运算有更复杂的处理（涉及逆元），在基础阶段我们暂不使用。

⚠️ 模运算的常见技巧¶

✅ 边计算边取模¶

防止中间数据溢出或超范围：

int res = 0;
for (int i = 0; i < n; i++) 
{
    res = (res + a[i]) % MOD; // 累加取模
}

类似地，乘法也要边乘边模：

int res = 1;
for (int i = 1; i <= n; i++) 
{
    res = 1ll * res * i % MOD; // 注意防止乘法溢出
}

✅ 防止负数¶

减法时应加一个模数再取模，避免出现负数：

int res = (a - b + MOD) % MOD;

📌 小结¶

模运算保持数值稳定，控制结果在 $[0, m - 1]$
模运算满足加、减、乘的封闭性和同余传递性
遇到除法先不做模，等掌握逆元后再处理
实际编程时：加法、乘法、减法操作都要边运算边模

模运算在组合数学、计数、动态规划等场景非常常见，是算法竞赛中的必修技能。