模运算与同余：让数字“转圈圈”的魔法

你有没有想过，为什么时钟上14点会变成下午2点？为什么判断一个数是不是偶数要看它除以2的余数？这些问题的答案都藏在一个叫“模运算”的小魔术里。简单说，模运算就是求余数 —— 比如10除以3，商是3，余数是1，在C++里写成 10 % 3，结果就是1。

模运算不仅好玩，还能帮我们防止数字过大而“爆掉”（溢出），在密码学、闰年判断、星期计算等地方都大显身手。而“同余”则是模运算的好兄弟，它告诉我们两个数除以同一个数后，剩下的“零头”一样。

1. 生活中的模运算

时钟：12小时制，14点就是14 mod 12 = 2，所以是下午2点。
星期几：今天是星期三，那么100天后是星期几？ (3 + 100) mod 7 = 103 mod 7 = 5（星期五）。
零花钱：你每天存5元，攒了30天，妈妈又给了你20元，你想知道这些钱平均分给4个朋友后还剩多少？ (5×30 + 20) % 4 = 170 % 4 = 2（还剩2元）。

模运算的作用就是“转圈圈”，把数字限制在0到除数-1的范围内。

2. 同余：两个数字的“余数相同”关系

同余的意思是：两个数除以同一个除数，余数相同。比如：

14 ÷ 12 = 1 余 2，2 ÷ 12 = 0 余 2 → 14和2模12同余。
17 ÷ 5 = 3 余 2，7 ÷ 5 = 1 余 2 → 17和7模5同余。

记作：14 ≡ 2 (mod 12)，读作“14模12同余于2”。

同余在编程里特别有用，比如检查一个数能不能被另一个数整除：如果 a % b == 0，就说a能被b整除，也就是a ≡ 0 (mod b)。

3. C++中的取模运算符 %

在C++里，取模运算符 % 只用于整数（int、long long等），结果就是余数。例如：

#include <iostream>
using namespace std;

int main() {
    int a1 = 10, b1 = 3;          // 被除数和除数
    int remainder1 = a1 % b1;     // 10 % 3 = 1
    cout << "10 % 3 = " << remainder1 << endl;

    int a2 = 15, b2 = 5;          // 整除的情况
    int remainder2 = a2 % b2;     // 15 % 5 = 0
    cout << "15 % 5 = " << remainder2 << endl;

    int a3 = 7, b3 = 9;           // 被除数比除数小
    int remainder3 = a3 % b3;     // 7 % 9 = 7
    cout << "7 % 9 = " << remainder3 << endl;

    return 0;
}

运行结果：

10 % 3 = 1
15 % 5 = 0
7 % 9 = 7

常见用途：

判断奇偶：if (n % 2 == 1) 是奇数，if (n % 2 == 0) 是偶数。
判断闰年：年份能被4整除但不能被100整除，或者能被400整除。代码：if (year % 4 == 0 && year % 100 != 0 || year % 400 == 0)
控制数字范围：比如想生成0~9的随机数，rand() % 10。

4. 新手最容易犯的错：负数取模

C++里，% 的结果符号跟随被除数（左边那个数）。也就是说：

-5 % 3 结果是 -2（因为数学上 -5 = 3 × (-2) + 1，但C++计算为 -5 = 3 × (-1) + (-2)）。
5 % -3 结果是 2（被除数正，结果正）。
-5 % -3 结果是 -2（被除数负，结果负）。

然而，数学中我们通常想要一个非负的余数（0到除数-1）。所以在处理负数时，需要自己“校正”：

int a = -5, m = 3;
int mod_result = a % m;          // -2
int positive_mod = (a % m + m) % m;  // (-2 + 3) % 3 = 1

为什么加m再取模？ 因为加一个除数不改变同余关系（-2 ≡ 1 mod 3），而且把负数变成了正数。这个技巧叫“取正余数”，在循环队列、哈希表等场景很常用。

5. 模运算的四大性质（计算可以“偷懒”）

模运算的加法和乘法可以分开取模再合并，结果不变。这能防止中间数字太大导致溢出。

(a + b) % m = (a % m + b % m) % m
(a - b) % m = (a % m - b % m + m) % m（减法要注意加m防负）
(a * b) % m = (a % m * b % m) % m
(a / b) 不能直接取模（除法没有这个性质，需要用模逆元，那是更高阶的内容）

防止溢出的经典例子：

假设 a = 123456789, b = 987654321, m = 1000000007（一个常用的大质数）。

直接算 a * b，结果超过 int 的范围（约21亿），会溢出。但用性质：先把a和b分别对m取模，然后相乘，再取模。注意：两个 int 相乘可能还是超过 int，所以要用 long long：

#include <iostream>
using namespace std;

int main() {
    int a = 123456789, b = 987654321, m = 1000000007;  // 被乘数、乘数、模数
    // 用 long long 计算乘法取模
    long long product_mod = ( (long long)(a % m) * (b % m) ) % m;
    cout << "(a * b) mod m = " << product_mod << endl;   // 输出 725806483

    // 如果不取模直接乘，会溢出
    // int wrong = a * b;  // 溢出，结果错误
    // cout << wrong << endl;
    return 0;
}

注意：(long long)(a % m) 先转换成 long long 再乘，是为了避免两个 int 相乘时发生溢出。记住：乘法取模一定要用 long long。

6. 完整示例：计算星期几

小明的生日是6月1日，已知那天是星期六。请问100天后是星期几？

星期几可以用模7来计算，把星期六当作数字6（星期日=0，星期一=1……星期六=6）。那么100天后是 (6 + 100) % 7。

#include <iostream>
using namespace std;

int main() {
    int today = 6;                // 星期六 = 6
    int days_passed = 100;        // 经过的天数
    int future_day = (today + days_passed) % 7;  // 模7得到新星期数
    // 输出数字对应的星期名称
    cout << "100天后是星期";
    if (future_day == 0) cout << "日";
    else if (future_day == 1) cout << "一";
    else if (future_day == 2) cout << "二";
    else if (future_day == 3) cout << "三";
    else if (future_day == 4) cout << "四";
    else if (future_day == 5) cout << "五";
    else cout << "六";
    cout << "（数字" << future_day << "）" << endl;
    return 0;
}

输出：100天后是星期一（数字1） —— 因为6+100=106，106%7=1（星期一）。

7. 常见错误小结

错误	说明	正确做法
对浮点数用%	`%` 只用于整数，浮点数用 `fmod` 函数	用整数或者 `fmod`
忽略负数结果	以为 `-3%5` 是 2，实际是 -3	用 `(a%m + m)%m` 得到正余数
乘法溢出	`(a%m)*(b%m)` 结果仍可能超 int	强制转换为 `long long`
用 `%` 做除法	`a/b` 是商，`a%b` 是余数，不要混淆	分清商和余
忘记取模顺序	加法减法可以分开，除法不行	除法需要模逆元，避免直接取模

8. 相关知识点指引

判断闰年：结合模运算的整除判断。
快速幂：用模乘性质高效计算 (a^b) % m，防止幂运算溢出。
密码学中的模运算：RSA加密、哈希函数都大量使用模运算。
数论中的同余方程：如 ax ≡ b (mod m)，需要扩展欧几里得算法。
循环队列：用模运算实现数组的环形存取。

模运算虽然简单，却是整个计算机科学的基石之一。下次当你看到 % 符号时，记得它不仅是求余数，更是一把能控制数字“转圈圈”的魔法钥匙！

C++同余与模运算