欧几里得算法
众所周知的是，欧几里得算法可以用来求解最大公约数。它的核心是一个恒等式
，并且在
时函数值是 。C++14 标准提供一个函数
__gcd() 来求解最大公约数，而在 C++17 以后，我们可以使用
gcd() 和 lcm()
函数来求解两个数的最大公约数和最小公倍数。
通常我们采用递归版本：
1
2
3
| int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}
|
当然，C++ 标准使用的是循环版本：
1
2
3
4
5
6
7
8
| int gcd(int a, int b) {
while (b) {
int t = a % b;
a = b;
b = t;
}
return a;
}
|
扩展欧几里得算法
今天的重头戏是我们的扩展欧几里得算法（简称“扩欧”）。它和一般的朴素-扩展定理不太一样，按照常理，应该是一个针对互质（朴素）、一个针对不互质（扩展）。但是欧几里得算法并不存在互质和不互质的差别，因而也就没有这样的区分。扩展欧几里得算法能够在求解最大公约数的基础上连带求出不定方程
的特解，也算是在功能方面上的一种“扩展”吧。
贝祖定理
也就是
定理，它表述为：
对于任意不全为零的整数 ，总存在整数 ，使得 成立
我们可以利用这个定理来判断不定方程解的情况。
证明：
当 其一为 时，显然成立。
当 均不为 时，有一个结论是 。那么问题可以收缩到只考虑
同为正数时的情况了。接下来我们借用欧几里得算法的思路，即执行 直到
。假设初始参数为 ，并把欧几里得算法变为带余数的除法：
退出时 ，则 ，继续向上回代，最终得到
。两边同乘 得到原式。
因此在方程 中，如果
，那么是铁定无解的。
扩展欧几里得
假如我们拿到一个方程 ，并且已知它是有解的。我们一定可以把它化简成
的形式。根据欧几里得证明的最大公约数的等价变换，可以得到：
把取模换成带余除法，
就等价于 ，那么原式变为：
即，
发现这个式子和最开始的那个是同型的。也就是说我们每次递归的时候都需要把
减去
然后代入计算。递归终点和朴素欧几里得算法相同，在 时，原式为 ，可以返回特解 。注意传参时需要将 反着传入。
借助 C++ 的引用特性，可以在每次递归时计算。
1
2
3
4
5
6
7
8
9
| int exgcd(int a, int b, int &x, int &y) {
if (!b) {
y = 0, x = 1;
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
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll exgcd(ll a, ll b, ll &x, ll &y) {
if (!b) {
x = 1, y = 0;
return a;
}
ll d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t;
cin >> t;
while (t--) {
ll a, b, c, x, y;
cin >> a >> b >> c;
if (c % gcd(a, b) == 0) {
ll gcd = exgcd(a, b, x, y);
x *= c / gcd, y *= c / gcd;
ll low = ceil((1.0 - x) * gcd / b);
ll up = floor((y - 1.0) * gcd / a);
if (up < low) {
cout << (x + low * b / gcd) << ' ' << (y - up * a / gcd) << endl;
} else {
cout << up - low + 1 << ' ';
cout << (x + low * b / gcd) << ' ' << (y - up * a / gcd) << ' ';
cout << (x + up * b / gcd) << ' ' << (y - low * a / gcd) << endl;
}
} else cout << -1 << endl;
}
return 0;
}
|
乘法逆元
乘法逆元其实就是模意义下的倒数，因为取模是针对整数而言的，而实数域的倒数可能不是一个整数，所以引入一个乘法逆元的概念。定义线性同余方程
的解 为 在模 意义下的乘法逆元，记作 。
根据定义，我们其实就可以直接开始用扩展欧几里得计算了。特殊情况下，当
为质数时，由费马小定理得到 ，进而得 ，因此当 为质数时，逆元就是
的值，可以用快速幂解决（如果
特别大可以考虑十进制快速幂）。
根据带余除法，我们把同余方程变成这样：。有解的条件就是 ，只要 是 的倍数（包括 ），那么就不存在逆元。所以我们直接把
和 代入即可计算出逆元的值。注意解出的
可能为负数，那么就需要用
(x % MOD + MOD) % MOD 来将它转化为非负数。
调用 exgcd(a, p, x, y) 所得 即为逆元的值。
