贝祖定理#

也就是 定理，它表述为：

对于任意不全为零的整数 ，总存在整数 ，使得 成立

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

证明：

当 其一为 时，显然成立。

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

退出时 ，则 ，继续向上回代，最终得到 。两边同乘 得到原式。

因此在方程 中，如果 ，那么是铁定无解的。

扩展欧几里得#

假如我们拿到一个方程 ，并且已知它是有解的。我们一定可以把它化简成 的形式。根据欧几里得证明的最大公约数的等价变换，可以得到：

把取模换成带余除法， 就等价于 ，那么原式变为：

即，

发现这个式子和最开始的那个是同型的。也就是说我们每次递归的时候都需要把 减去 然后代入计算。递归终点和朴素欧几里得算法相同，在 时，原式为 ，可以返回特解 。注意传参时需要将 反着传入。

借助 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
}

不定方程的通解#

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

对于一个二元一次不定方程的基本式 ，显然有解。对于一般情况 ，满足 时才有解。一般式其实可以由基本式推导而来：。

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

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

我们一般只考虑整数解，所以需要保证 。显然当 时是可行的，方程的整数通解就可以通过如下形式导出：

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

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

解得：

因为 为整数，放缩得：

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

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
}

乘法逆元#

乘法逆元其实就是模意义下的倒数，因为取模是针对整数而言的，而实数域的倒数可能不是一个整数，所以引入一个乘法逆元的概念。定义线性同余方程 的解 为 在模 意义下的乘法逆元，记作 。

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

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

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