贝祖定理#

也就是 $\texttt{Bezout}$ 定理，它表述为：

对于任意不全为零的整数 $a,b$，总存在整数 $x,y$，使得 $ax+by=\gcd(a,b)$ 成立

我们可以利用这个定理来判断不定方程解的情况。

证明：

当 $a,b$ 其一为 ${0}$ 时，显然成立。

当 $a,b$ 均不为 ${0}$ 时，有一个结论是 $\gcd(a,b)=\gcd(a,-b)$。那么问题可以收缩到只考虑 $a,b$ 同为正数时的情况了。接下来我们借用欧几里得算法的思路，即执行 $\gcd(a,b)\rightarrow\gcd(b,a\bmod b)$ 直到 $b=0$。假设初始参数为 $a,b$，并把欧几里得算法变为带余数的除法：

退出时 $r_n=1$，则 $r_{n-2}-k_nr_{n-1}=1$，继续向上回代，最终得到 $ax+by=1$。两边同乘 $\gcd(a,b)$ 得到原式。

因此在方程 $ax+by=c$ 中，如果 $\gcd(a,b)\nmid c$，那么是铁定无解的。

扩展欧几里得#

假如我们拿到一个方程 $ax+by=c$，并且已知它是有解的。我们一定可以把它化简成 $ax+by=\gcd(a,b)$ 的形式。根据欧几里得证明的最大公约数的等价变换，可以得到：

把取模换成带余除法，$a\bmod b$ 就等价于 $a-\lfloor\frac{a}{b}\rfloor b$，那么原式变为：

即，

发现这个式子和最开始的那个是同型的。也就是说我们每次递归的时候都需要把 $x$ 减去 $\lfloor\frac{a}{b}\rfloor y$ 然后代入计算。递归终点和朴素欧几里得算法相同，在 $b=0$ 时，原式为 $ax+by=a$，可以返回特解 $x=1,y=0$。注意传参时需要将 $x,y$ 反着传入。

借助 C++ 的引用特性，可以在每次递归时计算。

1
int exgcd(int a, int b, int &x, int &y) {
2
    if (!b) {
3
        y = 0, x = 1;
4
        return a;
5
    }
6
    int d = exgcd(b, a % b, y, x);
7
    y -= (a / b) * x;
8
    return d;
9
}

不定方程的通解#

我们都知道，通过扩展欧几里得算法求出的 $x,y$ 是一组特解，而不定方程是可能存在无数组解的。我们需要找到这些解之间的规律，从而更加方便快捷地导出具有某些特殊性质的解来。

对于一个二元一次不定方程的基本式 $ax+by=\gcd(a,b)$，显然有解。对于一般情况 $ax+by=c$，满足 $\gcd(a,b)\mid c$ 时才有解。一般式其实可以由基本式推导而来：$a\frac{cx}{\gcd(a,b)}+b\frac{cy}{\gcd(a,b)}=c$。

一组特解为 $x_0,y_0$，根据上边的推导式，可以得到：

也因此，$ax_0+by_0=c$ 是成立的。假设有一个有理数 $\lambda$，显然下面的式子是成立的（拆开括号后会消去）：

我们一般只考虑整数解，所以需要保证 $\lambda b\in\mathbb Z,\lambda a\in\mathbb Z$。显然当 $\lambda=\frac{1}{\gcd(a,b)}$ 时是可行的，方程的整数通解就可以通过如下形式导出：

题目中还会给你一些限制条件，例如 $x,y$ 的最大/小正整数解分别是多少。此时需要进一步推导。

假如限制条件是，$x,y$ 均为正整数。那么有如下不等式组：

解得：

因为 $k$ 为整数，放缩得：

当右边严格小于左边时，无解，即没有 $x,y$ 同为正整数的解。否则，注意到 $x_1$ 与 $k$ 成正关系，$y_1$ 与 $k$ 成负关系。$x$ 的最大可能整数值就由 $k$ 的上界代入得出，$y$ 的最大可能整数值是 $k$ 的下界对应的值，反之亦然。

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
typedef long long ll;
5

6
ll exgcd(ll a, ll b, ll &x, ll &y) {
7
    if (!b) {
8
        x = 1, y = 0;
9
        return a;
10
    }
11
    ll d = exgcd(b, a % b, y, x);
12
    y -= a / b * x;
13
    return d;
14
}
15

16
int main() {
17
    ios::sync_with_stdio(false);
18
    cin.tie(nullptr);
19
    cout.tie(nullptr);
20

21
    int t;
22
    cin >> t;
23
    while (t--) {
24
        ll a, b, c, x, y;
25
        cin >> a >> b >> c;
26
        if (c % gcd(a, b) == 0) {
27
            ll gcd = exgcd(a, b, x, y);
28
            x *= c / gcd, y *= c / gcd; // 转化为推导式
29
            ll low = ceil((1.0 - x) * gcd / b); // 算下界，浮点数1.0是必须的
30
            ll up = floor((y - 1.0) * gcd / a); // 上界
31
            if (up < low) {
32
                cout << (x + low * b / gcd) << ' ' << (y - up * a / gcd) << endl; // x,y 最小值
33
            } else {
34
                cout << up - low + 1 << ' '; // 区间大小
35
                cout << (x + low * b / gcd) << ' ' << (y - up * a / gcd) << ' '; // x,y 最小值
36
                cout << (x + up * b / gcd) << ' ' << (y - low * a / gcd) << endl;// x,y 最大值
37
            }
38
        } else cout << -1 << endl;
39
    }
40
    return 0;
41
}

乘法逆元#

乘法逆元其实就是模意义下的倒数，因为取模是针对整数而言的，而实数域的倒数可能不是一个整数，所以引入一个乘法逆元的概念。定义线性同余方程 $ax\equiv1\pmod p$ 的解 $x$ 为 $a$ 在模 $p$ 意义下的乘法逆元，记作 $a^{-1}$。

根据定义，我们其实就可以直接开始用扩展欧几里得计算了。特殊情况下，当 $p$ 为质数时，由费马小定理得到 $a^{p-1}\equiv1\pmod p$，进而得 $a^{p-2}\equiv a^{-1}\pmod p$，因此当 $p$ 为质数时，逆元就是 $a^{p-2}\bmod p$ 的值，可以用快速幂解决（如果 $a,b$ 特别大可以考虑十进制快速幂）。

根据带余除法，我们把同余方程变成这样：$ax-py=1$。有解的条件就是 $\gcd(a,p)\mid 1$，只要 $a$ 是 $p$ 的倍数（包括 $0$），那么就不存在逆元。所以我们直接把 $a$ 和 $b=p$ 代入即可计算出逆元的值。注意解出的 $x$ 可能为负数，那么就需要用 (x % MOD + MOD) % MOD 来将它转化为非负数。

调用 exgcd(a, p, x, y) 所得 $x$ 即为逆元的值。