$\Huge\color{orchid}{点击此处获取更多干货}$

带有取模的乘法逆元

数学上的“乘法逆元”很直观，就是一个数的倒数，在带有取模的情况下，某个正整数$x$的乘法逆元就是满足$(x*y)\%m=1$的这个$y$，至于这个有什么用，相信各位对于“避免数字过大而将结果对某个数取模”这个需求不陌生了，这里先介绍一个“同余定理”：如果正整数$a,b,m$满足$\left | a-b \right | \% m=0$，则$a$与$b$模$m$同余，记作$a\equiv b(mod~m)$，在非负的情况下，若$c$为正整数，对于加、减、乘法来说$(a+c)\equiv (b+c)(mod~m)$，$(a-c)\equiv (b-c)(mod~m)$，$(a*c)\equiv (b*c)(mod~m)$，但是对于除法来说，如果$c$不能整除$a,b$，就没法继续计算了。

假设我们计算$(3*5/5)\%9$，直接计算就可以得出3，但考虑到有些计算结果实在太大，使用的编程语言又没有$\text{BigInteger}$这种超大整数类型（比如C/C++，有些计算结果让最牛掰的$\text{size_t}$都汗流浃背），这时候需要在每一步都使用同余定理去取模，那么$(3*5)\%9=6$，5不能整除6，得到了错误结果1.这个时候如果求出了5的模9乘法逆元11$((5*11)\%9=1)$，就可以转化为$(3*5*11)\%9=3$，因为$3*5*11=165=18*9+3$

假设用C++编程时，有一个很大的数$v$，大到超过了$\text{size_t}$的最大值，计算$(v/x)\%s$需要通过$v\%s=r$先得到较小的中间值$r$，但是在之后计算$(r/x)\%s$时由于$r\%x\ne 0$而无法继续推进了，这时候就可以用除数$x$的逆元$y$来计算$(r*y)\%s$，完成带有取模的加减乘除四种运算

计算乘法逆元的方法有多种，和上一条帖子所讲快速幂关联性最大的是费马小定理，它的表达式为：$x^{m-1}\%m=1$，其中$x$和$m$互质，即$gcd(x,m)=1$，不满足这个条件全都不存在逆元。表达式左侧也可以换成$x*x^{m-2}$，因此$x$的逆元就是$x^{m-2}$。这种方法在模数$m$为质数时有奇效

C++ 代码

最大公约数函数在$\text{numeric}$头文件里有，这里不再赘述

/**
 * @brief 求取模之下的逆元
 * @param e 待求元素
 * @param mod 模数
 * @return e的逆元
 * @retval 0 不存在逆元
 */
size_t inverseElement(size_t e, size_t mod) {
    if (gcd(e, mod) != 1) {
        return 0;
    }
    return quickPower(e, mod - 2, mod);
}

顺便复习一下快速幂的求法：

size_t quickPower(size_t base, size_t power, size_t mod) {
    size_t ans = 1;
    while (power > 0) {
        if (power & 1) {
            ans = (ans * base) % mod;
        }
        base = (base * base) % mod;
        power >>= 1;
    }
    return ans;
}