乘法逆元

在计算组合数 时，我们一般不会直接除以6，而是乘以6的乘法逆元（INV6)。

那么为什么要引入乘法逆元呢？根本原因在于，在取模运算的世界里，加减乘都满足分配律，唯独除法不行。

进一步地讲三个核心原因：

  1. 模运算中不能直接做除法

    假设我们要计算，如果我们对A B分别取模，拿结果一般是错误的

    比方说，正确的是，但是分别取模后却有，这逻辑上就崩溃了

  2. 防止中间过程的数值溢出

    对于这道题的，当然是可以的(因为 在 64 位整数 long long 的极限 之内)，但是在大多数算法题中，N通常会达到甚至更大，此时分子乘积会达到，连64位整数都会严重溢出。

    因此，我们需要每乘一次就取一次模：

    1
    2
    ans = E * (E - 1) % MOD;
    ans = ans * (E - 2) % MOD;

    但是，这又会有个问题：取了模之后，这个ans还能保证被6整除吗？并不行。

  3. 用“乘法逆元”代替“除法”

    既然不能除，数学家就想了一个办法：把除法变成乘法

    在普通的数学里，除以6等于乘以

    在模的世界里，我们也想找一个整数X，使得”乘以X取模“的效果，等同于”除以6取模“。这个神奇的X，就是 6 在模M下的乘法逆元（通常记作 ）。

    根据定义，乘法逆元满足：

    在我们的代码中，若，6的乘法逆元算出来正好是166666668，而恰好等于1

注. 计算过程： ，K = 1时，则有6X = 1000000008，即X = 166666668。当然如果除不尽，那就K往后面继续取 ↩

结论

有了乘法逆元，我们就可以肆无忌惮地在中间过程随时取模防溢出，最后只需把除以6替换成乘以166666668后取模，即：

这样既完美避开了“不能做除法”的数学限制，又解决了数据溢出的工程问题
相关文章

[[8-8-3-Euler-s-Sieve]]