在 LeetCode 刷题的时候，经常会遇到各种各样不同的取模的要求，有的时候是因为题目的要求太大要求我们取 1e9+7 这种取模，但更多的时候我们也会遇到加减乘除中不同的运算的时候的取模的情况。那么，具体的情况是什么样的呢，我们来看看具体的各种各样不同的情况(本博客参考了 0x3f 大佬的博客缩写，外带上自己的一点个人感悟，主要是便于自己复习理解)
取模的问题
本质上，负数取模的根源问题在于：当 a 为负数的时候，不同的标准对商的取整方向定义不同。在数学上来说，通常我们取余 a/n = q … r，通常我们希望余数 r 落在区间[0, n - 1]之间，但是在计算机的语言当中：
- C++/Java/JavaScript 是遵循趋于零截断的方式取余数的。例如-7 / 3 = -2.3333…, 截断后的商为-2，余数为 r = a - (n q) = -7 - (3 -2) = -1
- Python 通常是向下取整的，例如：-7 / 3 = -2.3333…，向下取整为-3。那么余数为 r = a - (n q) = -7 - (3 -3) = 2。
由上可见，在 C++和 js 等语言中，如果 a 是负数的话，a % MOD 的结果就会是一个负数。本质上，下面我们所有的讨论的目的就是让我们的计算结果强制映射回数学上的非负余数区间[0, MOD - 1]。
当我们在做各种各样不同的题目的时候，经常会因为一些问题而可能导致题目的答案非常的大，这个时候就会遇到一种情况，那就是我们的答案可能特别的大，这个时候可能会发生溢出或者大整数运算时间 TLE 的情况，那么如何正确的取模反而还成了一门重要的学问。
加法和乘法的取模
数学证明的能力
在 0x3f 大佬的博客中，有这样一个例子，如果让你计算 1234+6789 的个位数你会怎么进行计算？
轻而易举的，我们如果列出加法的竖式计算就不难发现，如果我们只是想要两个大数字经过加法运算之后答案的个位数，我们只需要用这两个大数字的个位相乘然后取这个个位的个位数即可。如上面的例子所列出的，我们这里只需要使用 4 + 9 = 13 mod 10 = 3 即可。
同样的，因为乘法是加法的变种运算，如果我们同样的列出乘法的竖式计算，我们也能得出这样的规律，两个数在进行乘法运算之后个位数上的数字只和个位上的数相关。所以：4 x 9 = 36 mod 10 = 6。
如果把上面的两个式子抽象成数学表达式，大概是这样的：
根据这两个恒等式，我们可以在这两个循环的计算过程中，对加分和乘法进行取模，而不是在循环之后取模。
WARNING如果我们这里涉及到幂运算，指数是不能随意取模的。如果指数在 64 位整数的范围内，可以用快速幂进行计算；如果指数超出了 64 位整数的范围，我们就需要欧拉降幂。
IMPORTANT如果计算的过程中有减法，可能会产生负数，处理不当也会导致神秘的错误。如何正确的处理这种情况呢？
同余
如果我们有两个不同的整数 x 和 y，如果(x-y) mod m = 0 (说明 x-y 是 m 的倍数)，则称 x 与 y 关于模 m 同余，记作
举个例子，42=== 12(mod 10), -17 === 3(mod 10)
同余是可以移项的
在同余式中的加减法可以移项： a+b === c+d(mod m) 可以通过移项得到 a-c === d-b 根据这个可以进行一些简单的推论
负数和减法的取模
根据同余的定义，我们有-17 === 3 (mod 10)。这里我们需要详细的讨论一下，首先，当 a - b 时，如果 a < b，那么会存在 a - b < 0 的情况，这种情况我们就要把负数上的结果给映射到正数中。用到的原理如下：加上一个 MOD 不会改变取模的结果，MOD === 0 (mod MOD)，但是他能够把结果从负值拉回到正值范围内。本质还是一个放缩的操作。
a % MOD：将 a 的绝对值缩小到 MOD 以内，即[-MOD + 1, MOD - 1]，+ MOD，如果是负数，则转换为整数，如果是整数，加完之后可能超过 MOD，% MOD，最后一步确保无论之前是正还是负数，结果最终落在[0, MOD - 1]当中。
怎么从 -17 得到 3？ 我们从-17+10+10 = 3。同样的，也可以进行 -17 mod 10 + 10 = -7 + 10 = 3，这样只需要加一次 m 就够了。 抽象出来，一般地，如果 x<0 且 0<=y<m，则 x===y(mod m)相当于
简单的来说，就是使用模 m 加 m 的方式，把 x 调整成为非负数。 为避免判断 x<0,更一般的写法是
这样无论 x 是正是负还是零，运算的结果都会落在[0, m - 1]中。 对于减法来说，当 a - b >= 0 时，前面的加法恒等式可以调整：
当代码实现的时候，不考虑在计算过程中产生的负数，最后使用(x mod m + m) mod m 调整。
除法的取模
如果要计算 24/8 mod 5，如果是小数的情况下我们无法计算取模的结果的。那么，如果 p 是一个质数，a 是 b 的倍数且 b 和 p 互质。
IMPORTANT1e9+7 是质数
那我们来记一下灵神给的结论
MOD = 1_000_000_007
// 加(a + b) % MOD
// 减，b 在 [0,MOD-1] 中(a - b + MOD) % MOD
// 把任意整数 a 取模到 [0,MOD-1] 中，无论 a 是正是负(a % MOD + MOD) % MOD
// 乘（注意使用 64 位整数）a * b % MOD
// 多个数相乘，要步步取模，防止溢出a * b % MOD * c % MOD
// 除（MOD 是质数且 b 不是 MOD 的倍数）a * qpow(b, MOD - 2, MOD) % MOD如果这篇文章对你有帮助，欢迎分享给更多人！
部分信息可能已经过时