前言

在算法题里,为了避免高精运算带来的种种不方便(高精实现不同影响效率,难对算法本身进行准确评估),所以经常需要对答案进行取模,我们都知道
(a × b) mod c = ((a mod c) × (b mod c)) mod c
(a + b) mod c = ((a mod c) + (b mod c)) mod c
(a - b) mod c = ((a mod c) - (b mod c)) mod c
可是除法却是一个意外。

正文

费马小定理 (Fermat's Little Theorem)

这东西高中选修就学过,初等数论的内容.
若p是质数,则对于任意整数a有a^p - a是p的倍数,或者说a^p在模p的情况下与a同余 (a^p ≡ a (mod p))。
若整数a不是p的倍数,则a^(p-1)在模p的情况下与1同余。

扩展欧几里得算法 (Extended Euclidean Algorithm)

贝祖定理 (Bézout's identity)

若a, b是整数,且gcd(a, b)=d, 则存在一对整数x, y, ax + by都一定是d的倍数,且一定存在整数x, y使得ax + by = d.

欧几里得算法 (Euclid's Algorithm)

两个整数的最大公约数 (Greatest Common Divisor)等于其中较小的那个数和两数相除余数的最大公约数.
或者说,设函数gcd(a, b)是求a和b的最大公约数,则对于任意整数a, b有 gcd(a, b) = gcd(b, a mod b).

正文

扩展欧几里得算法是欧几里得算法的扩展,给定整数a, b,快速求解贝祖定理中的x与y.
假设已经求得了 b×x_1 + (a % b) × y_1 = gcd(a, b) 的整数解x_1和y_1.
再将 a%b = a-(a/b)×b 代入后就得到 a×y_1+b×(x_1-(a/b)×y_1) = gcd(a, b)
而当 b = 0 时则有 a×1 + b×0 = a = gcd(a, b)

C语言实现:
int extgcd(int a, int b, int &x, int &y) {
    int d = a;
    if (b != 0) {
        d = extgcd(b, a % b, y, x);
        y -= (a / b) * x;
    } else {
        x = 1;
        y = 0;
    }
    return d;
}

线性同余方程 (Linear Congruence Equation)

ax ≡ b (mod n),此方程有解当且仅当 b 能够被 a 与 n 的最大公约数整除,也就是 gcd(a,n) | b.
这个方程等价于ax - b是n的倍数,我们不妨设为-y倍数,那么方程可以改写成 ax + ny = b.
所以我们可以先利用扩展欧几里得算法求出一组整数x_1和y_1,满足a×x_1 + n×y_1 = gcd(a, n)
然后 x = x_1 × b / gcd(a, n) 就是原线性方程的一个解。

乘法逆元 (Multiplicative Inverse Modulo)

好的,我们来说乘法逆元,这是群论的内容,但是在这里我们不扯群论,只说怎么算。
若b, m互质,且b|a,则存在一个整数x,使得a/b ≡ a×x (mod m),称x为b的模m乘法逆元,记为 b^(-1) (mod m).
因为 a/b ≡ a × b^(-1) ≡ a/b × a × b^(-1) (mod m),所以b × b^(-1) ≡ 1 (mod m)
我们先来求m是质数的情况,此时设为p,并且 b < p.
根据费马小定理知,b^(p-1) ≡ 1 (mod p),即 b×b^(p-2) ≡ 1 (mod p),因此当模数p为质数时,b^(p-2)就是b的乘法逆元.
那么m不是质数的情况,我们可以同过求解线性同余方程得知.