取模与取余

Python 里用 % 得到余数（取模/取余），用 // 得到整除结果。LeetCode 里常用于循环下标、奇偶判断、哈希分桶等。

基本用法

正数时：余数在 [0, b-1]

被除数是正数时，a % b 的结果一定在 0 到 b-1 之间，很适合做循环下标和哈希桶。

奇偶判断

n % 2 == 0 表示偶数，n % 2 == 1 表示奇数。

哈希分桶

用 x % m 把数映射到 0..m-1，常用于哈希表桶下标、环形缓冲区。

负数取模（了解即可）

Python 的 % 结果符号与除数一致，且满足 (a // b) * b + a % b == a。刷题时多数是正数运算，遇到负数可先转成「等价正数」再取模。

divmod(a, b)：一次拿到商和余数

Python 里有个很实用的内置函数 divmod(a, b)，会返回 (a // b, a % b)，很多题里能让代码更清爽。

同余（刷题高频）

如果 a % m == b % m，我们说 a 与 b 在模 m 意义下同余。同余最常用在：循环/周期、环形数组、前缀和取模、分组计数。

模运算有一些非常好用的“可变形”规则（适用于整数）：

• (a + b) % m == ((a % m) + (b % m)) % m
• (a - b) % m == ((a % m) - (b % m)) % m
• (a * b) % m == ((a % m) * (b % m)) % m

前缀和取模：统计“能整除”的子数组（思路示例）

这是模运算在 LeetCode 里非常经典的用法之一：统计子数组和能被 m 整除的数量。

核心点：如果两个前缀和 pre[i] 与 pre[j] 满足 pre[i] % m == pre[j] % m，那么 (pre[i] - pre[j]) % m == 0，对应的区间和可整除。

大数取模：避免中间结果变得很大

很多题会让你输出结果对 (10^9+7) 取模（记作 MOD = 1_000_000_007）。做法是：每一步加/乘之后立刻 % MOD，保持数不爆炸、也更快。

常见坑

• 负数下标/往前走：写成 (i - k) % n 在 Python 里也能工作，但为了跨语言/更直观，常写 (i - k + n) % n。
• // 是向下取整：-7 // 3 == -3，这会影响你推导负数相关的取模。
• % 和数学里的“余数”定义不同：Python 的 % 满足“余数与除数同号”，并保持 (a // b) * b + a % b == a 恒成立。

小结