CC++ & Algorithm

Python同余与模运算

较难3
语言版本：C++Python
概述：同余就是两个数除以同一个数后余数相同，就像钟表上3点和15点都指向同一个位置。

和钟表做朋友——Python中的模运算与同余

你有没有看过钟表上的时间？比如现在是下午3点，表盘上指的却是3，而不是15——因为钟表只有12个小时。这就是模运算在生活中的经典例子。模运算就是求两个数相除的余数，而同余告诉我们，两个数在“除以同一个数”这件事上可以看成是等价的。

在Python里，模运算用 % 符号来表示，它可是个超级有用的工具，能帮我们处理循环、判断奇偶、推算星期几、甚至设计密码。下面我们一起来把它彻底搞懂！

1. 什么是模运算？—— 分剩余数

模运算就是求余数。比如你有8块糖，要分给3个小朋友，每人拿2块，剩下2块。用Python算一下：

candies = 8      # 糖的数量
kids = 3         # 小朋友人数
remainder = candies % kids  # 求出余数
print(remainder)  # 输出 2

再看一个和分数有关的例子：你考了90分，老师说要按10分一档给等级（90～100为A，80～89为B……），那90分属于哪一档？其实用 90 % 10 得到0，说明它是整10的倍数，属于A档的起点。

生活里到处都是模运算：

  • 钟表：15点变成下午3点，因为 15 % 12 = 3。
  • 星期：今天是星期三，100天后是星期几？(3 + 100) % 7 然后处理余数为0的情况。
  • 排队报数：10个人报数“1、2、3、1、2、3……”，可以用 (位置 % 3) 或者 (位置 - 1) % 3 + 1 来得到该报的数字。

2. 什么是同余？—— “除后剩一样”

同余就是两个数除以同一个数，余数相同。比如15和3，除以12都余3，我们就说“15和3对于模12是同余的”，数学上写成： 15≡3(mod12)15 \equiv 3 \pmod{12}

在Python里，判断两个数是否同余，就是比较它们的余数是否相等：

# 判断 25 和 13 模 12 是否同余
print(25 % 12 == 13 % 12)   # 输出 True，因为都余1

# 判断 23 和 11 模 12 是否同余
print(23 % 12 == 11 % 12)   # 输出 True，因为23%12=11，11%12=11，都是11

同余就像一个等价标签：只要余数一样，这些数字在“模m”的世界里就被当成同一个东西。钟表上，3点、15点、27点……都指向同一个位置，因为它们模12都是3。

3. 同余的神奇性质——加减乘都不变

如果两个数同余，那么它们的和、差、积仍然同余。听起来有点绕，但用例子一下就明白了。

例如：7和1模3同余（因为7%3=1，1%3=1），3和0模3同余（3%3=0，0%3=0）。那么：

  • 和：7+3=10，1+0=1 → 10%3=1，1%3=1，同余！
  • 差：7-3=4，1-0=1 → 4%3=1，1%3=1，同余！
  • 积：7×3=21，1×0=0 → 21%3=0，0%3=0，同余！

这个性质在编程里很有用，比如做大数运算时可以先取模再计算，防止数字太大。看一段代码验证一下：

# 验证同余的加减乘性质
a, b = 7, 3          # 两个数
m = 3                # 模数
# 计算原始余数
rem_a = a % m        # 7%3=1
rem_b = b % m        # 3%3=0

# 和
sum_original = (a + b) % m          # (7+3)%3=10%3=1
sum_via_remainder = (rem_a + rem_b) % m  # (1+0)%3=1
print(f"和同余: {sum_original == sum_via_remainder}")  # True

# 差
diff_original = (a - b) % m
diff_via_remainder = (rem_a - rem_b) % m
print(f"差同余: {diff_original == diff_via_remainder}")  # True，注意负余数用%会变成正数

# 积
prod_original = (a * b) % m
prod_via_remainder = (rem_a * rem_b) % m
print(f"积同余: {prod_original == prod_via_remainder}")  # True

4. 模运算的常见应用——从判断奇偶到周期循环

模运算几乎无处不在，下面介绍几个最常用的场景。

4.1 判断奇数和偶数

任何整数模2，余数为0就是偶数，余数为1就是奇数：

num = 17               # 要判断的数字
if num % 2 == 0:
    print(f"{num} 是偶数")
else:
    print(f"{num} 是奇数")  # 输出这个

4.2 判断整除

如果 a % b == 0，说明a能被b整除。比如判断一个数是不是3的倍数：

number = 81            # 一个数
if number % 3 == 0:
    print(f"{number} 是3的倍数")  # 输出
else:
    print(f"{number} 不是3的倍数")

4.3 星期几的推算（周期循环）

你已经看到例子：已知今天是星期几，求n天后是星期几。记得把余数0处理成星期日（或第7天）。更严谨的做法是用 (today + days_later - 1) % 7 + 1 来保证结果在1~7之间。

today = 1             # 假设1代表周一，7代表周日
days_later = 100      # 100天后
future = (today + days_later - 1) % 7 + 1  # 结果在1~7
print(f"100天后是星期{future}")  # 计算后是星期二（2）

4.4 循环队列、循环报数

比如有10个人围成一圈报数，第1个人报1，第2个人报2……第10个人报10，然后第11个人又报1。如果知道一个人的序号（从1开始），想得到他报的数，可以用 (序号 - 1) % 10 + 1。

person = 15            # 第15个人
total_people = 10      # 一共10个人
number = (person - 1) % total_people + 1  # 报的数
print(f"第{person}个人报数字{number}")  # 输出 5

5. 新手容易犯的错——负数和比较陷阱

错误一：负数模运算的结果可能让你困惑

在Python中，a % b 的结果总是与 b的正负号相同（余数非负）。比如 -7 % 3 的结果是2，因为 -7除以3，商是-3，余数是2（因为-3*3 + 2 = -7）。这和数学上的同余定义一致，但初学者容易觉得应该是-1。

  • 记住：Python的 % 总返回非负余数（如果b>0）。
  • 如果希望余数恒为正，可以写 (a % b + b) % b。
print(-7 % 3)   # 输出 2，不是 -1
print(7 % -3)   # 输出 -2（因为b=-3，余数也是负的）

错误二：误以为同余就是相等

同余只是余数相等，不代表两个数本身相等。比如 25 % 12 == 13 % 12 成立，但 25≠13。写代码时要注意，比较的是 a % m == b % m，而不是直接比较 a==b。

错误三：忘记处理余数为0的特殊情况

在星期推算、循环编号时，如果余数为0，通常需要将其转换为最大值（比如星期天对应7，或者队列中最大序号）。很多新手忘记这步，导致结果出现0。

6. 完整可运行示例——一个“时间与数字”小工具

下面这个程序把模运算的几个用处组合在一起：判断奇偶、推算星期、判断整除、同余关系检测。你可以直接复制运行。

# 完整示例：模运算综合应用
print("=== 模运算小工具 ===")

# 1. 判断奇偶
num = 2024                    # 年份
if num % 2 == 0:
    print(f"{num} 是偶数年")
else:
    print(f"{num} 是奇数年")

# 2. 判断闰年（能被4整除但不能被100整除，或能被400整除）
year = 2024                   # 要判断的年份
if (year % 4 == 0 and year % 100 != 0) or (year % 400 == 0):
    print(f"{year} 是闰年，有366天")
else:
    print(f"{year} 不是闰年")

# 3. 星期推算：已知2024年1月1日是星期一，求1月31日是星期几
jan_first = 1                 # 1月1日是周一（数字1）
day_of_month = 31             # 1月31日
days_passed = day_of_month - 1  # 距离1月1日已经过了30天
future_weekday = (jan_first + days_passed - 1) % 7 + 1
print(f"{year}年1月{day_of_month}日是星期{future_weekday}")

# 4. 同余判断：验证两个数模12是否同余
a_value = 37                  # 第一个数
b_value = 61                  # 第二个数
modulus = 12                  # 模数
if a_value % modulus == b_value % modulus:
    print(f"{a_value} 和 {b_value} 模 {modulus} 同余")
else:
    print(f"{a_value} 和 {b_value} 模 {modulus} 不同余")

# 5. 循环报数：8个人，第20个人报几号？
people = 8                    # 总人数
person_number = 20            # 第几个人
call_out = (person_number - 1) % people + 1
print(f"第{person_number}个人报数字 {call_out}")

运行结果示例：

=== 模运算小工具 ===
2024 是偶数年
2024 是闰年，有366天
2024年1月31日是星期三
37 和 61 模 12 不同余
第20个人报数字 4

7. 相关知识点指引

模运算和同余是初等数论的基石，学好它之后，可以继续探索：

  • 整除与最大公约数：用辗转相除法（欧几里得算法）求最大公约数，里面大量用到模运算。
  • 同余方程：比如 ax ≡ b (mod m) 怎么解，这是密码学的基础。
  • RSA加密：利用大数模幂运算实现加解密，安全又神奇。
  • 校验码：身份证最后一位、ISBN书号都用到了模11或模10的校验算法。

如果你已经掌握了模运算，可以试试用 % 实现一个猜数字游戏（每次猜完后告诉你“大了还是小了”，并记录剩余猜测次数），或者斐波那契数列末位数字的快速计算（只用模10）。这些练习会帮你把模运算用得更熟练！

例题精讲

1单选题

已知 a ≡ b (mod m), c ≡ d (mod m)，m 为正整数，下列选项中一定成立的是？

Aa + c ≡ b + d (mod m)
Ba × c ≡ b × d (mod m)
Ca^2 ≡ b^2 (mod m)
D以上都对
2判断题

在模运算中，若 a ≡ b (mod m)，则一定有 a mod m = b mod m（假设取非负余数）。

3填空题
下面的函数用于计算 a 的 b 次幂模 m 的值（快速幂算法），其中 a,b,m 均为正整数，m ≤ 10^9。请补全代码。
def mod_pow(a: int, b: int, m: int) -> int:
    res = 1
    a %= m
    while b > 0:
        if b % 2 == 1:
            res = ___①___
        a = ___②___
        b //= 2
    return res
4单选题

在模 m 的运算中，一个整数 a 存在模 m 下的乘法逆元的充分必要条件是：

Aa 能被 m 整除
Ba 和 m 互质
Ca 是质数
Dm 是质数
5填空题
以下代码使用费马小定理计算组合数 C(n, k) 模 1 000 000 007（质数），其中 n, k 为正整数且 n ≤ 10^6。请补全函数 com(n,k) 中的缺失部分。
MOD = 1000000007
fact = [1] * (1000001)
for i in range(1, 1000001):
    fact[i] = fact[i-1] * i % MOD

def modinv(x):
    return pow(x, MOD-2, MOD)

def com(n, k):
    if k < 0 or k > n:
        return 0
    return fact[n] * modinv(fact[k]) % MOD * ___①___ % MOD