扩展欧几里得算法
扩展欧几里得定理：设 和 不全为 ，则存在整数 和 ，使得 。
证明：设 ，求 的一组 。
欧几里得算法可知，。
即 ，。
则 。
可以通过欧几里得算法递归迭代到 时可以得到此时 ，再利用上面推出的 与 的关系进一步代入计算，得到 的一组解。
利用归纳法，最后解的大小满足：。
1
2
3
4
5
6
7
8
9
10
11
12
| int exgcd (int a, int b, int &x, int &y) {
if (!b) {
x = 1, y = 0;
return a;
}
int d = exgcd (b, a % b, y, x);
y -= (a / b) * x;
return d;
}
|
欧拉定理 & 费马小定理
欧拉定理：若 ，则 。
证明：设 是模 的缩系，因为 ，所以 也是模 的缩系。
即 。
根据缩系性质，可约去 ，即得 。
费马小定理：若 为素数，则 。
证明：当 为素数 ，由于 ，带入欧拉定理可立即得到费马小定理。
线性同余方程
设 ，则一次同余方程：，有解的充要条件是 。
设同余方程有解 ，则 ，从而 ，但 ，故 。
反过来，若 ，则同余方程与 同解，任取模 的一个完系 ，因 ， 也是模 的完系，所以同余方程存在整数解，且形成模 的一个同余类。但 时，原同余方程（模 ）恰有 个解。
1
2
3
4
5
6
7
8
9
| int x, y;
int d = exgcd (a, p, x, y);
if (b % d) {
res = -1;
} else {
x *= (b / d);
res = (x % (p / d) + (p / d)) % (p / d);
}
|
中国剩余定理
中国剩余定理：设 是两两互素的正整数，则对于任意整数 ，一次同余方程组 必有解，且全部解是模 的一个同余类。确切地说，同余方程组的解是 。
其中 及 由条件 决定。因为 ，故有整数 ，使得 。对 ，有 ，因此数 ，满足： （对 ）。
易于验证，上面的解的”叠加“ 满足同余方程组的解。
另一方面，如果 都是同余方程组的解，则 。由 两两互素知，，因此同余方程组的解是模 的一个同余类。
线性同余方程组
模数互质，使用中国剩余定理。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| vector <int> A(n), B(n);
LL M = 1;
for (int i = 0; i < n; i ++ ) {
cin >> A[i] >> B[i];
M *= A[i];
}
LL res = 0;
for (int i = 0; i < n; i ++ ) {
LL Mi = M / A[i];
LL ti, x;
exgcd (Mi, A[i], ti, x);
res += B[i] * Mi * ti;
}
cout << (res % M + M) % M << "\n";
|
在模数不互质的情况下，设其中两个方程分别是 。转化为不定方程：，其中 是整数，则有 。由裴蜀定理，当 不能被 整除时，无解；否则，扩展欧几里得定理得到一组可行解 ，则这两个方程组的解是 ，其中 。多个方程两两合并。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| LL res = 0, m1, a1;
cin >> m1 >> a1;
for (int i = 0; i < n - 1; i ++ ) {
LL m2, a2;
cin >> m2 >> a2;
LL k1, k2;
LL d = exgcd (m1, m2, k1, k2);
if ((a2 - a1) % d) {
res = -1;
}
k1 *= (a2 - a1) / d;
k1 = (k1 % (m2 / d) + (m2 / d)) % (m2 / d);
LL m = abs (m1 / d * m2);
a1 = k1 * m1 + a1;
m1 = m;
}
if (res != -1) {
res = (a1 % m1 + m1) % m1;
}
cout << res << "\n";
|