a % b 是求 a / b 的余数，这种运算叫做模运算，模运算是数论中的一个很重要的内容。

逆元的意义

我们知道，在模运算中，有以下公式成立：
(a + b) % m == ((a % m) + (b % m)) % m
(a - b) % m == ((a % m) - (b % m)) % m
(a * b) % m == ((a % m) * (b % m)) % m
这三个公式有什么用呢？就是在计算结果灰常灰常大的时候，我们只需要得到它对某个数(比如1,000,000,007)的余数即可，这种情况下，如果计算过程中的数不是很大，而且只有加法、减法和乘法，那我们就可以在计算过程中不断取余，这样得到的结果也是正确的。
这就造成了一件很尴尬的事，假如计算过程中出现除法该怎么办，要知道上述规律对于除法是不成立的！
在数学运算中：a / b == a * (1 / b)，其中1 / b叫b的倒数。那么在模运算中，有没有这种类似于倒数的存在呢？答案是有！它就是乘法逆元！

如何计算逆元

方法一：扩展欧几里德算法
如果你还不了解扩展欧几里德算法，可以看其他方法，也可以移步这里《求解最大公约数 - 欧几里德算法》简单了解一下。
我们知道扩展欧几里德算法除了可以计算出a和b的最大公约数d以外，还能求出a * x + b * y = d的整数解。
如果存在等式a * p - m * q == 1，那么此时(a * p) % m == 1，于是p就是整数a对于整数m的逆元。而这个等式可以很简单的套入扩展欧几里德算法中求解，于是求逆元的代码如下：（C++语言，其中exgcd(int, int, int &, int, int)的实现见《求解最大公约数 - 欧几里德算法》）

int mod_inverse(int a, int m)
{
    int d, p, q;
    exgcd(a, m, d, p, q);
    return (p % m + m) % m;
}

这个算法的的时间复杂度和扩展欧几里德算法的时间复杂度一样，都是O(logN)。同时我们也很容易看出来，当a和m的最大公约数不等于1时，逆元不存在。

方法二：不知道什么名的推导
这个方法是上次从胡光大牛那里学来的，很流弊，很好用，简单记载于此。
我们还是要求a相对于m的逆元a'，这里a < m。
此时存在k * a + q == m，即k * a + q ≡ 0 (mod m)，这里k = ⌊m / a⌋, q = m % a。（≡是同余符号）
在等式两边同时乘以a' * q'，其中a'是a的逆元，q'是q的逆元，得到：k * q' + a' ≡ 0 (mod m)。
移项得a' = -k * q'，这里于是代码如下：（C++语言）

int mod_inverse(int a, int m)
{
    if(a == 0) return -1;  // can not found a mod inverse number
    if(a == 1) return 1;
    int ret = mod_inverse(m % a, m);
    if(ret == -1) return ret;
    return (-m / a * ret % m + m) % m;
}

这个算法的复杂度是O(logN)的，我们还可以在O(m)的时间内递推出1,2,3...m的逆元，代码如下：

inv[0] = -1;
inv[1] = 1;
for(int i = 2; i <= m; i++)
{
    if(inv[m % i] == -1) {
        inv[i] == -1);
    } else {
        inv[i] = (-m / i * inv[m % i] % m + m) % m;
    }
}

方法三：费马小定理
费马小定理：若p为素数，则x^p ≡ x (mod p)。（x^p为x的p次方）
所以x^(p - 1) ≡ 1 (mod p)，所以x^(-1) ≡ x^(p - 2) (mod p)，x^(-1)即为x的逆元。
所以，当p为素数时，我们可以使用快速幂来很简单的计算出整数x对于p的逆元。

标签: 算法, 数论