二元一次不定方程和扩展欧几里得

二元一次不定方程

定义

已知 ，解出关于 的方程的整数解，方程形如：

有解的条件

裴蜀定理 (Bézout’s Identity)

对于任意整数 ，方程 有整数解 的充要条件是 是 和 的最大公约数 的倍数。 ^167556

简单来说：

如果 ，则方程有整数解。
否则，方程无整数解。

为什么？

是 a 和 b 的最大公约数，所以 a 能被 整除，b 也能被 整除。
那么 这个整体，也一定能被 整除。
如果 不能被 整除，那么 这个等式就不可能成立。

扩展欧几里得（Exgcd）求解

特解

对于方程

我们设

由于

得到

将 写作 ，整理得到

所以得到一组 特解：

在 时，原方程为 ，得到的特解为

一般解

对于更一般的方程

检查是否有解

根据

![[二元一次不定方程和扩展欧几里得#^167556]]

判断是否有解。

求特解

设 ，解出方程 的一组特殊解 。

那么

即
$$
ax+by=c \Rightarrow

$$
这就是一组特解。

将解缩放

代码实现

返回解的方式

auto exgcd(int a, int b) {
    if(b == 0)
        return make_pair(1, 0);
    auto [x, y] = exgcd(b, a % b);
    return make_pair(y, x - (a / b) * y);
}

传引用的方式

void exgcd(int a, int b, int &x, int &y) {
    if (b == 0)
        return x = 1, y = 0, void();
    int x_hat, y_hat;
    exgcd(b, a % b, x_hat, y_hat);
    x = y_hat, y = x_hat - (a / b) * y_hat;
}

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

题目描述

给定不定方程

若该方程无整数解，输出 。
若该方程有整数解，且有正整数解，则输出其正整数解的数量，所有正整数解中 的最小值，所有正整数解中 的最小值，所有正整数解中 的最大值，以及所有正整数解中 的最大值。
若方程有整数解，但没有正整数解，你需要输出所有整数解中 的最小正整数值， 的最小正整数值。

正整数解即为 均为正整数的解， 不是正整数。
整数解即为 均为整数的解。
的最小正整数值即所有 为正整数的整数解中 的最小值， 同理。

输入格式

第一行一个正整数 ，代表数据组数。

接下来 行，每行三个由空格隔开的正整数 。

输出格式

行。

若该行对应的询问无整数解，一个数字 。
若该行对应的询问有整数解但无正整数解，包含 个由空格隔开的数字，依次代表整数解中， 的最小正整数值， 的最小正整数值。
否则包含 个由空格隔开的数字，依次代表正整数解的数量，正整数解中， 的最小值， 的最小值， 的最大值， 的最大值。

读入输出量较大，注意使用较快的读入输出方式

输入输出样例 #1

输入 #1

7
2 11 100
3 18 6
192 608 17
19 2 60817
11 45 14
19 19 810
98 76 5432

输出 #1

4 6 2 39 8
2 1
-1
1600 1 18 3199 30399
34 3
-1
2 12 7 50 56

说明/提示

【数据范围】

对于 的数据，，。

题解

若该方程无整数解，输出 −1。

令 ll g = gcd(a, b) ，若 c % g != 0，则方程无整数解。

这一个判断

好的，我们来详细解析这道模板题 P5656【二元一次不定方程 (exgcd)】。

这道题目是关于求解线性丢番图方程（Linear Diophantine Equation）的典型问题，并在此基础上增加了对解的性质（是否为正整数解）的讨论。

题目核心

核心问题是求解方程：

其中 是给定的正整数，我们需要找出整数解 ，并根据解的情况进行分类讨论。

Step 1: 判断是否有整数解

这是最基本的一步。
令 。
根据裴蜀定理的推论，我们检查 c % g 是否等于 0。

• 如果 c % g != 0，方程无整数解。根据题目要求，输出 -1。
• 如果 c % g == 0，方程有整数解。我们继续下一步。

Step 2: 求出一组特解

我们使用 exgcd(a, b) 得到一组解 满足 。
然后，将这个解进行放缩，得到 的一组特解 ：


注意：由于 范围可达 ，这里的 可能会非常大，甚至超出 long long 的范围。但我们后续可以对它进行处理。

Step 3: 找出通解公式

一旦我们有了一组特解 ，就可以推导出所有的整数解。
假设 是另一组整数解，则有：


两式相减得到：


两边同时除以 ：

因为 ，即 和 互质，所以 必须是 的倍数。
我们可以设 ，其中 是任意整数。
代入上式，得到 。

于是，我们得到了方程的通解公式：


其中 为任意整数。为了方便，我们记 ，。

Step 4: 处理特解 过大的问题

直接使用 可能会导致 很大，不利于后续计算。我们可以利用通解的性质，将 调整到一个较小的范围内。
例如，我们可以让新的 满足 。这可以通过取模实现：

这样调整了 之后，对应的 也需要更新，但我们不需要重新计算，因为新的 和 仍然是方程的一组解。可以直接通过原方程计算新的 ：

这个除法一定是整除。经过这样的处理，我们的特解 就不会有溢出的风险了。

Step 5: 分析正整数解

现在我们要找的是满足 且 的解。根据通解公式，这等价于求解满足下面两个不等式的整数 ：

综合起来，我们需要找到满足以下条件的整数 ：

我们令 和 。
这里的向上取整和向下取整需要用整数运算小心处理，特别是对于负数。

• floor(A/B) 对于正数 B，在 C++ 中可以直接用 A/B 实现。
• ceil(A/B) 对于正数 B，在 C++ 中可以写成 (A + B - 1) / B（仅当 A > 0 时），一个更通用的写法是 (A > 0) ? (A + B - 1) / B : A / B。

Step 6: 根据 的范围分类输出

现在我们有了 的取值范围 ，可以根据这个范围来判断解的情况。

情况一：有正整数解
如果 ，说明存在至少一个整数 满足条件，即方程有正整数解。

• 正整数解的数量: 。
• 的最小值: 。因为 ， 随着 的增大而增大。所以最小的 对应最小的 ，即 。
  。
• 的最小值: 。因为 ， 随着 的增大而减小。所以最小的 对应最大的 ，即 。
  。
• 的最大值: 对应最大的 ，即 。
  。
• 的最大值: 对应最小的 ，即 。
  。
  按顺序输出这 5 个值。

情况二：无正整数解
如果 ，说明不存在满足条件的整数 ，即方程没有正整数解。
此时，题目要求我们输出所有整数解中， 的最小正整数值和 的最小正整数值。

• 的最小正整数值: 我们需要找到最小的 。这等价于找到最小的整数 使得 。这个 正是上面我们求出的 ！
  所以， 的最小正整数值就是 。
• 的最小正整数值: 我们需要找到最小的 。这等价于找到最大的整数 使得 。这个 正是上面求出的 ！所以对应的 值是 。
  注意：这里的 和 虽然不构成一个有效的区间，但它们本身是有意义的： 是能使 成为正整数的最小 值， 是能使 成为正整数的最大 值。
  按顺序输出这两个值。

另一种更简洁的思路（避免处理 k）

上面通过分析 的范围来求解是通用的方法。但此题也可以直接计算边界值，避免显式计算 ，从而绕开复杂的取整运算。

1. 求 的最小正整数值 min_x
   所有 的解构成一个等差数列，公差为 。我们要求这个数列中大于等于 1 的最小值。
   这等价于求 x₀ 在模 b' 意义下的最小正同余数。
   一个稳健的计算方法是： min_x = (x₀ % b' + b' - 1) % b' + 1; (这行代码需要仔细理解，它能正确处理 x₀ 是正数、负数、0 的情况)。

2. 求 的最小正整数值 min_y
   同理，所有 的解构成公差为 的等差数列。
   min_y = (y₀ % a' + a' - 1) % a' + 1;

3. 判断是否有正整数解
   我们已经找到了最小的正 值 min_x。我们计算出与它配对的 值：
   y_at_min_x = (c - a * min_x) / b;
   如果 y_at_min_x >= 1，那么 (min_x, y_at_min_x) 就是一组正整数解。这说明存在正整数解。

4. 分类输出

   • 有正整数解 (y_at_min_x >= 1):
     • x 的最小正整数解就是 min_x。
     • y 的最小正整数解就是 min_y。
     • 和 是负相关的。 最大的解对应 最小的解。所以与 min_y 配对的 就是 的最大值 max_x。
       max_x = (c - b * min_y) / a;
     • 同理， 的最大值 max_y 与 min_x 配对。
       max_y = y_at_min_x;
     • 解的数量就是从 min_x 到 max_x 以 为步长有多少个数。
       count = (max_x - min_x) / b' + 1;
     • 输出 count, min_x, min_y, max_x, max_y。
   • 无正整数解 (y_at_min_x < 1):
     • 此时直接输出所有整数解中 的最小正整数值和 的最小正整数值即可。
     • 输出 min_x, min_y。

这种方法思路更清晰，代码实现也更简洁。

注意事项

• 数据范围: 高达 ，exgcd 计算过程以及中间变量（如特解）都必须使用 long long 类型以防溢出。
• 快速 I/O: 的数量很大（），需要使用 scanf/printf 或者更快的读写模板，cin/cout 在不解除同步的情况下可能会超时。

C++ 代码实现 (采用第二种思路)

#include <iostream>
#include <numeric> // For std::gcd in C++17, but we'll write our own for exgcd

// Fast I/O
void fast_io() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
}

// Extended Euclidean Algorithm
// Solves ax + by = gcd(a, b)
// Returns gcd(a, b) and finds x, y by reference
long long exgcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long g = exgcd(b, a % b, y, x);
    y -= (a / b) * x;
    return g;
}

void solve() {
    long long a, b, c;
    scanf("%lld %lld %lld", &a, &b, &c);

    long long x, y;
    long long g = exgcd(a, b, x, y);

    // Case 1: No integer solution
    if (c % g != 0) {
        printf("-1\n");
        return;
    }

    // Scale x and y to get a particular solution for ax + by = c
    // Note: using __int128 to prevent intermediate overflow before modular reduction
    __int128 x0 = (__int128)x * (c / g);
    
    long long b_prime = b / g;
    long long a_prime = a / g;

    // Find the minimum positive x
    // x = x0 + k * b_prime >= 1
    // We want the smallest positive value in the congruence class of x0 (mod b_prime)
    long long min_x = (x0 % b_prime + b_prime) % b_prime;
    if (min_x == 0) min_x = b_prime; // or min_x += b_prime; if it was 0

    // Calculate the corresponding y for min_x
    long long y_at_min_x = (c - a * min_x) / b;

    // If y at min_x is not positive, then there are no positive integer solutions
    if (y_at_min_x <= 0) {
        // Case 2: Integer solutions exist, but no positive integer solutions
        // We need min positive x and min positive y independently.
        // We already have min_x. Now find min_y.
        __int128 y0 = (__int128)y * (c / g);
        long long min_y = (y0 % a_prime + a_prime) % a_prime;
        if (min_y == 0) min_y = a_prime;
        
        printf("%lld %lld\n", min_x, min_y);
    } else {
        // Case 3: Positive integer solutions exist
        // Find min_y for the positive solutions.
        // y = y_at_min_x - k * a_prime >= 1
        // We want the smallest positive value in the congruence class of y_at_min_x (mod a_prime)
        long long min_y = (y_at_min_x % a_prime + a_prime) % a_prime;
        if (min_y == 0) min_y = a_prime;

        // Find max_x for the positive solutions. This corresponds to min_y.
        long long max_x = (c - b * min_y) / a;
        
        // Find max_y for the positive solutions. This corresponds to min_x.
        long long max_y = y_at_min_x;

        // Number of solutions
        long long count = (max_x - min_x) / b_prime + 1;
        
        printf("%lld %lld %lld %lld %lld\n", count, min_x, min_y, max_x, max_y);
    }
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        solve();
    }
    return 0;
}