这篇文章上次修改于 402 天前，可能其部分内容已经发生变化，如有疑问可询问作者。

算法学习笔记(8): 同余

前置知识：

整除：当 A / B 为一个整数，则称 B 整除 A 符号记作：B|A
同余：同余是一种二元关系，需要第三者作为模也就是 A % p == B % p记作A ≡ B (mod p)
逆元：若 ab ≡ 1 (mod p) ，则a、b互为逆元
剩余系：对于一个特定的正整数n，一个整数集中的数模n所得的余数域

基础性质：

自反性：A ≡ A (mod p)
对称性：若 A ≡ B (mod p) 则有 B ≡ A (mod p)
传递性：若 A ≡ B (mod p) A ≡ C (mod p) 则有 B ≡ C (mod p)

当A ≡ B (mod p) C ≡ D (mod p) ，有

加法： A + C ≡ B + C (mod p)
减法： A - C ≡ B - C (mod p)
乘法： AC ≡ BC (mod p)
同余的幂：k 和 m 大于0 都是整数

线性丢番图方程性质

ax + by = c 这是一个二元线性丢返图方程，其中 a、b、c是已知变量，x、y是未知数且要求是整数。

该方程只有0解和无数解

定理一：ax + by = c 有解 ←→ gcd (a, b) | c

设 d = gcd (a, b) 则有 dm = a ，d n = b

也就是d ( mx + n y ) = c 易得

同时通解 x = x0 + (b / d) n (n 为整数)

例题一：

给定两个格点(x1, y1) (x2, y2)，求线段上的整数坐标点数量。

题解：

先获得线段的方程 (y2 - y1) x + (x1 - x2) y = y2x1 - y1x2

对应 a b c d，可得 d = gcd (|y2 - y1|, |x1 - x2|)

x = x1 + (x1 - x2) / d * n (x1 < x < x2)

可得n有d -1种取值，也就有d - 1个点。

PICK定理：

如果有个多边形的四个点都是整数坐标，则其面积 S = 边界上格点数 / 2 + 内部格点数 - 1

扩展欧几里得算法

目的是求ax + by = gcd(a,b)的整数解

欧几里得算法又称作辗转相除法，对于两个数不断取余数，直到得出最大公因数的过程。

例如我们求gcd(A, B); 有以下过程

其中，最后的rn就是gcd(A, B); 可知在计算gcd时，q值是毫无意义的，但是一旦结合以下式子，q的值就会被利用，从而该算法被称为“扩展”

又因为 rn = gcd(A, B)，所以我们要求的x和y分别也就是sn和tn。它们也可以从递推公式中算出，即可获得解。这就是扩展欧几里得算法

代码实现

using i64 = long long;
i64 extendGcd(i64 a, i64 b, i64 &x, i64 &y){
	if(b == 0){
		x = 1;
        y = 0;
        return a;
    }
    i64 d = extendGcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

线性丢番图方程求解

已知线性丢番图方程的通解，此时需要得到一个特解作为前提。

求特解使用了扩展欧几里得算法

我们记 d = gcd(a, b)，扩展欧几里得算法求的解也就是ax0 + by0 = d

线性丢番图方程是ax + by = c又因为d|c所以

a(x0 * c / d) + b(y0 * c / d) = d * c / d

线性丢番图方程的特解也就是

x1 = x0 * c / d 和 y1 = y0 * c / d

可得通解为：

x = x1 + (b / d) n和 y = y1 - (a / d) n

一元线性同余方程：

设x为未知数，给定a、b、m 求 x 满足 ax ≡ b ( mod m )

已知他们同余，则m|ax - b 设 ax - b = - y m (-y 是倍数)，也就是 ax + my = b 一个线性丢番图方程。

对于这个方程，一旦x有一解 x = x1, 则有 x = x1 + km 无数个解。故我们考虑解的个数为模m不同余数的解

定理：

当gcd(a, m) | b 时有 d - 1 个模m不同余数的解。通解记作：

x = x0 + (m / d) n [n取0, 1, 2, … d - 1]

当gcd(a, m) = 1时，有唯一的模m不同余的解。

例子：luogu1082 求逆

求关于 x 的同余方程 ax ≡ 1 ( mod b ) 的最小正整数解。

即求 ax + by = 1

题目要有解，故gcd(a, b) | 1也就是gcd(a, b) = 1

故可以使用拓展欧几里得算法算得特解x0

通解也就是 x = x0 + bn, 再找最小正整数解即可。

i64 getAns(i64 a, i64 b){
    i64 x, y;
    extendGcd(a, b, x, y); // Xans = x + n * (b / 1); 通解公式
    return (x % b + b) % b;
}

int main(){
    i64 a, b;
    cin >> a >> b;
    cout << getAns(a, b) << endl;
}

费马小定理

内容：有n是素数，a与n互质，a^{n-1} ≡ 1 mod(n)

也就是 a 与 a ^ {n - 2} 互为逆元。

用逆元解同余方程

对于求解同余方程 ax ≡ b (mod m)，如果有 a mod m的一个逆，便可在原方程两端乘以这个逆设逆为T

则有 aTx ≡ bT (mod m) 也就是 x = bT (mod m)

逆元作用

对于计算一些大数的运算，题目通常会取模以保证运算。

对于A * B * C 我们可以 A * B % MOD * C % MOD 确保计算的过程中不会溢出。

但是对于除法，如果有A * B * C / D 这种方法就不奏效了，因为在取模的过程中，原本可以被D整除的数就会损失，所以这个方法在除法上不可行。

为了保证能正常的对大数相除取模，我们可以运用同余的原理

例如 A / B ≡ r (mod m)

因此，我们要找到b的逆元，一般的题目中m都是质数，也就是说在m为质数前提，根据费马小定理：

A / B (mod m) = AB^(m - 2) mod m

至于B^(m - 2)可以使用快速幂即可

总结

逆元在数字较大的题目中频繁出现，作为理解题目的前提，是解决难题的必会知识

Mai Icy