在 LeetCode 刷题的时候，经常会遇到各种各样不同的取模的要求，有的时候是因为题目的要求太大要求我们取 1e9+7 这种取模，但更多的时候我们也会遇到加减乘除中不同的运算的时候的取模的情况。那么，具体的情况是什么样的呢，我们来看看具体的各种各样不同的情况(本博客参考了 0x3f 大佬的博客缩写，外带上自己的一点个人感悟，主要是便于自己复习理解)

取模的问题#

当我们在做各种各样不同的题目的时候，经常会因为一些问题而可能导致题目的答案非常的大，这个时候就会遇到一种情况，那就是我们的答案可能特别的大，这个时候可能会发生溢出或者大整数运算时间 TLE 的情况，那么如何正确的取模反而还成了一门重要的学问。

加法和乘法的取模#

数学证明的能力#

在 0x3f 大佬的博客中，有这样一个例子，如果让你计算 1234+6789 的个位数你会怎么进行计算？

轻而易举的，我们如果列出加法的竖式计算就不难发现，如果我们只是想要两个大数字经过加法运算之后答案的个位数，我们只需要用这两个大数字的个位相乘然后取这个个位的个位数即可。如上面的例子所列出的，我们这里只需要使用 4 + 9 = 13 mod 10 = 3 即可。

同样的，因为乘法是加法的变种运算，如果我们同样的列出乘法的竖式计算，我们也能得出这样的规律，两个数在进行乘法运算之后个位数上的数字只和个位上的数相关。所以：4 x 9 = 36 mod 10 = 6。

如果把上面的两个式子抽象成数学表达式，大概是这样的：

(a+b)mod m = ((a mod m) + (b mod m)) mod m (a*b)mod m = ((a mod m) * (b mod m)) mod m

根据这两个恒等式，我们可以在这两个循环的计算过程中，对加分和乘法进行取模，而不是在循环之后取模。

WARNING
如果我们这里涉及到幂运算，指数是不能随意取模的。如果指数在 64 位整数的范围内，可以用快速幂进行计算；如果指数超出了 64 位整数的范围，我们就需要欧拉降幂。

WARNING
如果计算的过程中有减法，可能会产生负数，处理不当也会导致神秘的错误。如何正确的处理这种情况呢？

同余#

如果我们有两个不同的整数 x 和 y，如果(x-y) mod m = 0 (说明 x-y 是 m 的倍数)，则称 x 与 y 关于模 m 同余，记作

x===y (mod m)

举个例子，42=== 12(mod 10), -17 === 3(mod 10)

同余是可以移项的#

在同余式中的加减法可以移项： a+b === c+d(mod m) 可以通过移项得到 a-c === d-b 根据这个可以进行一些简单的推论

负数和减法的取模#

根据同余的定义，我们有-17 === 3 (mod 10)。怎么从-17 得到 3？我们从-17+10+10 = 3。同样的，也可以进行 -17 mod 10 + 10 = -7 + 10 = 3，这样只需要加一次 m 就够了。抽象出来，一般地，如果 x<0 且 0<=y<m，则 x===y(mod m)相当于

x mod m + m = y

简单的来说，就是使用模 m 加 m 的方式，把 x 调整成为非负数。为避免判断 x<0,更一般的写法是

(x mod m + m) mod m

这样无论 x 是正是负还是零，运算的结果都会落在[0, m - 1]中。对于减法来说，当 a - b >= 0 时，前面的加法恒等式可以调整：

((a-b)mod m = (a mod m) - (b mod m) + m) mod m

当代码实现的时候，不考虑在计算过程中产生的负数，最后使用(x mod m + m) mod m 调整。

除法的取模#

如果要计算 24/8 mod 5，如果是小数的情况下我们无法计算取模的结果的。那么，如果 p 是一个质数，a 是 b 的倍数且 b 和 p 互质。

WARNING
1e9+7 是质数

那我们来记一下灵神给的结论

1
MOD = 1_000_000_007
2

3
// 加
4
(a + b) % MOD
5

6
// 减，b 在 [0,MOD-1] 中
7
(a - b + MOD) % MOD
8

9
// 把任意整数 a 取模到 [0,MOD-1] 中，无论 a 是正是负
10
(a % MOD + MOD) % MOD
11

12
// 乘（注意使用 64 位整数）
13
a * b % MOD
14

15
// 多个数相乘，要步步取模，防止溢出
16
a * b % MOD * c % MOD
17

18
// 除（MOD 是质数且 b 不是 MOD 的倍数）
19
a * qpow(b, MOD - 2, MOD) % MOD