【LeetCode-C】Sep 2025

取模

取模运算（Modulo Operation）遵循一系列重要的运算律，这些规则在与加、减、乘和幂运算结合时尤其有用。下面通过一个表格汇总了它的主要运算律，并附上了简要说明和应用提示。

运算类型	运算律	数学表达式	说明
基本运算	模加	`(a + b) % p = (a % p + b % p) % p`	和的模等于模的和再取模。这可以防止中间结果溢出。
	模减	`(a - b) % p = (a % p - b % p) % p`	注意：结果可能为负，通常需调整：`(a % p - b % p + p) % p`
	模乘	`(a * b) % p = (a % p * b % p) % p`	积的模等于模的积再取模。同样有助于避免大数相乘溢出。
	模幂	`a^b % p = ((a % p)^b) % p`	幂的模等于底数取模后再求幂并取模。是快速幂算法的基础。
结合律	模加结合律	`((a+b) % p + c) % p = (a + (b+c) % p) % p`	模加法满足结合律，意味着分组计算不影响最终结果。
	模乘结合律	`((ab) % p c) % p = (a * (b*c) % p) % p`	模乘法满足结合律，计算顺序可调整。
交换律	模加交换律	`(a + b) % p = (b + a) % p`	模加法满足交换律，顺序可交换。
	模乘交换律	`(a * b) % p = (b * a) % p`	模乘法满足交换律，顺序可交换。
分配律	乘法对模加分配律	`((a + b) % p * c) % p = ((a * c) % p + (b * c) % p) % p`	模运算下，乘法对加法满足分配律。

这些运算律的核心价值在于，它们允许我们在进行加、减、乘、幂运算时，随时对中间结果取模而不影响最终结果的正确性（相对于同样的运算最后再取模而言）。这能有效防止计算过程中数值过大而导致的溢出问题，在编程和算法设计中非常重要。

此外，取模运算还与同余关系密切相关。如果 a ≡ b (mod p)（表示 a和 b除以 p的余数相同），那么对于任意整数 c，通常有：

除法（逆元）：表格中未列出直接的模除运算律。因为普通的除法分配律在模运算中并不成立（即 (a / b) % p ≠ (a % p) / (b % p) % p）。在模运算中，“除法”通常通过乘以其模逆元来实现，但这要求 b与 p互质。
负数取模：不同编程语言对负数取模的结果定义可能不同（主要区别在于商向0舍入还是向负无穷舍入），这会影响到 a % p的具体值（可能为负）。上述部分运算律（如模减）在涉及负数时，为了确保得到非负结果，可能需要额外的调整（如加上 p再取模）。

虽然“取模”和“取余”都得到除法后的余数，但对于负整数，两者的结果可能不同。

区别主要源于商向哪个方向取整：
- 取余 (Remainder): 商向 0 取整 (truncated division)。结果的符号与被除数 a相同。常见于 C/C++、Java、JavaScript 等语言中的 %运算符。
- 取模 (Modulo): 商向 负无穷 取整 (floored division)。结果的符号与除数 p相同。常见于 Python、Ruby 等语言中的 %运算符。
示例 (-7 mod 4或 -7 % 4):
- 取余操作（商向0取整）：c = trunc(-7/4) = trunc(-1.75) = -1, 余数 r = -7 - (-1)*4 = -3。
- 取模操作（商向负无穷取整）：c = floor(-7/4) = floor(-1.75) = -2, 余数 r = -7 - (-2)*4 = 1。
当 a和 p同号时，两者结果相同；异号时则不同。在编程时，务必了解你所用语言的 %运算符定义。

掌握这些运算律能帮助你在许多计算场景中更加得心应手。