【模板】二元一次不定方程 (exgcd)

题意

给定方程：

$a x + b y = c$

需要分情况输出：

若无整数解，输出 $-1$
若有正整数解，输出正整数解个数，以及这些正整数解里 $x$ / $y$ 的最小值和最大值
若有整数解但没有正整数解，输出所有整数解里 $x$ 的最小正整数值、 $y$ 的最小正整数值

思路

先看一个更直接的小数据暴力：

cpp

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while (T--) {
        i64 a, b, c;
        cin >> a >> b >> c;

        vector<pair<i64, i64> > all_sol;

        for (i64 x = -200; x <= 200; x++) {
            for (i64 y = -200; y <= 200; y++) {
                if (a * x + b * y == c) {
                    all_sol.push_back(make_pair(x, y));
                }
            }
        }

        if (all_sol.empty()) {
            cout << -1 << '\n';
            continue;
        }

        vector<pair<i64, i64> > pos_sol;
        i64 min_pos_x = (1LL << 60);
        i64 min_pos_y = (1LL << 60);

        for (size_t i = 0; i < all_sol.size(); i++) {
            i64 x = all_sol[i].first;
            i64 y = all_sol[i].second;
            if (x > 0 && x < min_pos_x) {
                min_pos_x = x;
            }
            if (y > 0 && y < min_pos_y) {
                min_pos_y = y;
            }
            if (x > 0 && y > 0) {
                pos_sol.push_back(all_sol[i]);
            }
        }

        if (!pos_sol.empty()) {
            sort(pos_sol.begin(), pos_sol.end());
            i64 xmin = pos_sol.front().first;
            i64 xmax = pos_sol.back().first;
            i64 ymin = (1LL << 60), ymax = 0;
            for (size_t i = 0; i < pos_sol.size(); i++) {
                ymin = min(ymin, pos_sol[i].second);
                ymax = max(ymax, pos_sol[i].second);
            }
            cout << pos_sol.size() << ' ' << xmin << ' ' << ymin << ' ' << xmax << ' ' << ymax << '\n';
        }
        else {
            cout << min_pos_x << ' ' << min_pos_y << '\n';
        }
    }

    return 0;
}

暴力版在一个小范围里枚举所有 $x, y$ ，直接检查：

$a x + b y == c$

这样写能帮助理解输出含义，但显然不能处理大数据。

关键观察还是扩展欧几里得的标准结论：

若：

$d = \gcd(a, b)$

那么方程：

$a x + b y = c$

有整数解的充要条件是：

$d$ 能整除 $c$

如果不能整除，直接输出 $-1$ 。

若能整除，先用 exgcd 求出：

$a x_0 + b y_0 = d$

再整体乘上 $c / d$ ，得到一组特解。

通解形式

设：

$step\_x = b / d$
$step\_y = a / d$

则所有整数解都可以写成：

$x = x_0 + k \times step\_x$
$y = y_0 - k \times step\_y$

这里 $k$ 是任意整数。

正整数解怎么求

若要求 $x > 0, y > 0$ ，只要把这两个条件分别改写成对 $k$ 的不等式：

$x_0 + k \times step\_x \geqslant 1$
$y_0 - k \times step\_y \geqslant 1$

于是就能得到：

$k$ 的下界
$k$ 的上界

如果下界不超过上界，就说明有正整数解。

这张图表达的就是这个过程：

flowchart LR
  A["通解：x=x0+k·step_x"] --> C["把 x>0, y>0 变成 k 的区间"]
  B["通解：y=y0-k·step_y"] --> C
  C --> D["区间非空 => 有正整数解"]

图里真正要看的，是"问题已经不再是求 $x,y$ "，而是转成了"求参数 $k$ 的合法范围"。

没有正整数解时输出什么

若整数解存在，但正整数解区间为空，那么题目要求输出：

所有整数解中 $x$ 的最小正整数值
所有整数解中 $y$ 的最小正整数值

这其实就是：

$x$ 在模 $step\_x$ 意义下的最小正剩余
$y$ 在模 $step\_y$ 意义下的最小正剩余

代码

cpp

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using i128 = __int128_t;

i64 exgcd(i64 a, i64 b, i64 &x, i64 &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }

    i64 d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

i64 floor_div(i128 a, i128 b) {
    if (b < 0) {
        a = -a;
        b = -b;
    }
    if (a >= 0) {
        return (i64) (a / b);
    }
    return (i64) (-((-a + b - 1) / b));
}

i64 ceil_div(i128 a, i128 b) {
    if (b < 0) {
        a = -a;
        b = -b;
    }
    if (a >= 0) {
        return (i64) ((a + b - 1) / b);
    }
    return (i64) (-((-a) / b));
}

i64 min_positive_residue(i64 x, i64 mod) {
    i64 r = (x % mod + mod) % mod;
    if (r == 0) {
        r = mod;
    }
    return r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while (T--) {
        i64 a, b, c;
        cin >> a >> b >> c;

        i64 x0, y0;
        i64 d = exgcd(a, b, x0, y0);

        if (c % d != 0) {
            cout << -1 << '\n';
            continue;
        }

        i64 mul = c / d;
        i64 step_x = b / d;
        i64 step_y = a / d;

        i128 x = (i128) x0 * mul;
        i128 y = (i128) y0 * mul;

        // 通解：
        // x = x0 + k * step_x
        // y = y0 - k * step_y
        i64 kl = ceil_div(1 - x, step_x);
        i64 kr = floor_div(y - 1, step_y);

        if (kl <= kr) {
            i64 cnt = kr - kl + 1;
            i64 xmin = (i64) (x + (i128) kl * step_x);
            i64 xmax = (i64) (x + (i128) kr * step_x);
            i64 ymax = (i64) (y - (i128) kl * step_y);
            i64 ymin = (i64) (y - (i128) kr * step_y);
            cout << cnt << ' ' << xmin << ' ' << ymin << ' ' << xmax << ' ' << ymax << '\n';
        }
        else {
            i64 xmin = min_positive_residue((i64) x, step_x);
            i64 ymin = min_positive_residue((i64) y, step_y);
            cout << xmin << ' ' << ymin << '\n';
        }
    }

    return 0;
}

复杂度

每组数据主要是一次 exgcd 和若干常数次计算：

$O(\log \max(a,b))$

空间复杂度：

$O(1)$

总结

这题最核心的不是 exgcd 本身，而是通解形式：

$x = x_0 + k \times b/d$
$y = y_0 - k \times a/d$

一旦把这个通解写出来，后面所有输出要求都只是围绕 $k$ 的范围做分类讨论。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。