LeetCode 刷题

两数相加、两数相乘怎么求余数，负数求余数到底等于多少，如何高效求余数？这篇文章将记录这些知识，方便后续查阅。

正数求余

自然数对正数求余是指将一个自然数除以另一个正整数后得到的余数。

例如，对于自然数 $a$ 和正整数 $m$，求 $a/m$ 的余数，可以用符号「%」表示，即 $a \% m$。

假设 $a=km+r, (a>=0, m>0)$，那么 $a/m$ 等于 $k, (k>=0)$，$a \% m$ 等于 $r, (0<=r<m)$。

两数相加求余

结论：一般地，两个整数相加后求余数，有如下等式：

$$\begin{cases} (a + b) \% m \\ = ((a \% m) + (b \% m)) \% m \\ \end{cases}$$

证明：根据 带余除法，任意整数 $a$ 都可以表示为 $a=km+r$，这里 $r$ 相当于 $a \% m$。那么设 $a=k_{1}m+r_{1}, b=k_{2}m+r_{2}$，则有

$$\begin{cases} (a + b) \% m \\ = ((k_{1} + k_{2})m + r_{1} + r_{2}) \% m \\ = (r_{1} + r_{2}) \% m \\ = ((a \% m) + (b \% m)) \% m \\ \end{cases}$$

证毕。

两数相乘求余

结论：一般地，两个整数相乘后求余数，有如下等式：

$$(a \times b) \% m = ((a \% m) \times (b \% m)) \% m$$

证明：根据 带余除法，任意整数 $a$ 都可以表示为 $a=km+r$，这里 $r$ 相当于 $a \% m$。那么设 $a=k_{1}m+r_{1}, b=k_{2}m+r_{2}$，则有

$$\begin{cases} (a \times b) \% m \\ = ((k_{1}k_{2})m^{2} + (k_{1}r_{2} + k_{2}r_{1})m + r_{1}r_{2}) \% m \\ = (r_{1}r_{2}) \% m \\ = ((a \% m) \times (b \% m)) \% m \\ \end{cases}$$

证毕。

负数求余

不同语言的负数求余

1. 一个负数对一个正数求余数：

• C、C++ 和 Java 的结果是商尽可能大（在坐标轴上尽可能靠右），余数的正负号与被除数的正负号保持一致，即为负数。
• Python、Google 计算器和百度计算器的结果是商尽可能小（在坐标轴上尽可能靠左），余数的正负号与除数的正负号保持一致，为正数。

2. 一个正数对一个负数求余数：

• C、C++ 和 Java 的结果是商尽可能大（在坐标轴上尽可能靠右），余数的正负号与被除数的正负号保持一致，即为正数。
• Python、Google 计算器和百度计算器的结果是商尽可能小（在坐标轴上尽可能靠左），余数的正负号与除数的正负号保持一致，为负数。

3. 一个负数对一个负数求余数：

• C、C++ 和 Java 以及 Python、Google 计算器和百度计算器的结果都是商尽可能小（在坐标轴上尽可能靠左），余数为负数。

总结

1. 在被除数与除数 正负号相同时 ，所有语言 都期望商尽可能小 （ 余数的正负号与被除数、除数的正负号一致）。
2. 在被除数与除数 正负号相反时：

• 对于 C、C++ 和 Java，期望商尽可能大 （ 余数的正负号与 被除数 的正负号保持一致）；
• 对于 Python、Google 计算器和百度计算器，还是期望商尽可能小 （ 余数的正负号与 除数 的正负号保持一致）。

位运算求余数

对于自然数 $a$ 和正整数 $m$，在某些情况下，当 $m=2^n$ 时，有如下替换公式：

$$a \% m = a \& (m - 1)$$

即:

$$a \% 2^{n} = a \& (2^{n} - 1)$$

希望这次看起来更清晰了！

参考资料：

1. 灵茶山艾府 Leetcode2731 移动机器人题解
2. 实数范围内的求模（求余）运算：负数求余究竟怎么求
3. 使用位操作（& 运算）代替求余操作