二元一次不定方程：用硬币凑钱也能玩出数学

这个方程到底在干什么？

你有没有遇到过这样的问题：手里只有两种面额的硬币，比如3元和5元，想买一个8元的冰淇淋，能不能正好付清？或者跟同学凑钱买零食，你带5元，他带7元，要凑出24元，行不行？这些问题都可以用一个数学方程来解决，它就是二元一次不定方程。

简单说，形如
$a x + b y = c$
的方程就叫二元一次不定方程。其中 $a, b, c$ 是已知的整数（比如硬币面额和目标金额）， $x$ 和 $y$ 是未知的整数（分别代表两种硬币的个数）。我们不但要判断有没有整数解，还要把所有可能的整数解都找出来。

乍一看这跟小学学的解方程很像，但不同的是：x和y只要求是整数，而且往往有无穷多组解，所以叫“不定”方程。比如6x+10y=2，你试几个：(2,-1)、(7,-4)、(-3,2)……全都是解。这种方程在生活中很常见，比如拼钱、分配任务、安排车辆。

生活中的更多例子（不只是凑硬币）

例子1：零花钱凑整

小明每周零花钱是3元，小红每周零花钱是5元。他们想合买一个价值14元的文具套装，各自出整数周的零花钱（不能拆分），能不能正好？设小明出x周的钱，小红出y周的钱，方程就是：
$3x + 5y = 14$
试一下：x=3时，9+5y=14 => 5y=5 => y=1，成立！所以小明出3周（9元），小红出1周（5元），正好14元。

例子2：分糖果

老师有40颗糖，要分给两种不同的人数：每组4人或者每组6人。问能不能正好分完？设分4人组x组，6人组y组，总人数是4x+6y。但这里方程是4x+6y=40，求整数解。gcd(4,6)=2，40能被2整除，所以有解。一个解是x=1,y=6（4+36=40）。注意x和y不能是负数，所以还要限制非负。

例子3：负数也有意义

有时候解会出现负数，比如用6元和10元的硬币凑出2元，我们找到62+10(-1)=2。y=-1意味着你实际付出了10元，但找回了8元？或者理解为你想用10元硬币去买东西，但售货员找你2元？所以负数在现实生活中代表“找零”或“借出”，数学上允许它存在，但实际应用时我们常常只取非负解。

数学原理：为什么有解需要满足一个条件？

有解的条件

二元一次不定方程 $ax+by=c$ 有整数解的充要条件是：
$\gcd(a,b) \mid c$
（读作：a和b的最大公约数整除c）

为什么？你可以这样想：

无论x和y取什么整数，ax+by的值一定是gcd(a,b)的倍数。因为gcd(a,b)能整除a和b，所以也能整除它们的任何线性组合。
所以如果c不是gcd(a,b)的倍数，方程绝对无解。
反过来，如果c是gcd(a,b)的倍数，我们可以先找到ax+by=gcd(a,b)的一组解，然后两边乘以c/gcd，就得到了原方程的解。

例如：6x+10y=2，gcd(6,10)=2，2能被2整除，所以有解。而6x+10y=3，3不能被2整除，所以无解。

通解的推导（用脑子想象一下）

假设我们已经通过扩展欧几里得算法找到了一组特解 $(x_0, y_0)$ 满足
$a x_0 + b y_0 = \gcd(a,b)$
如果c是gcd的k倍，那么原方程的一组特解就是
$x_1 = k x_0,\quad y_1 = k y_0$
然后，所有整数解可以写成：

\begin{cases} x = x_1 + \dfrac{b}{\gcd(a,b)} \cdot t \$$1em] y = y_1 - \dfrac{a}{\gcd(a,b)} \cdot t \end{cases} \quad t \text{为任意整数}

为什么这样写？因为当你把x和y的表达式代入原方程时，含有t的那两项会相互抵消（想想： $a \cdot \frac{b}{g} t - b \cdot \frac{a}{g} t = 0$ ）。所以无论t取什么，总是原来的值c。

生活比喻：想象你沿着一条直线走，起始点是特解，每步（b/g）或（a/g）就像步长，走一步x增加，y减少，但总和不变。

求解步骤（一步步来，别怕）

计算最大公约数：用欧几里得算法求 $g = \gcd(a,b)$ 。
检查整除：如果 $c \% g \neq 0$ ，直接说“无解”，结束。
求一组特解：用扩展欧几里得算法求出 $a x_0 + b y_0 = g$ 的一组整数解。
放大：令 $k = c / g$ ，则原方程的一组特解为 $x_1 = k x_0,\ y_1 = k y_0$ 。
写通解：
$x = x_1 + (b/g) * t$
$y = y_1 - (a/g) * t$
其中t为任意整数。

注意：如果a或b是负数，步长符号可能会变，但原理一样。一般我们会先把系数转为正数来处理。

新手最容易犯的4个错误

忘记检查整除条件
直接拿扩展欧几里得求出特解就用，结果发现不是原方程的解。实际上扩展欧几里得求的是ax+by=gcd的解，不检查c是不是gcd的倍数就直接乘以c，会得到错误结果。一定要先判断 c % g == 0。
通解符号搞反
通解公式是 $x = x_1 + (b/g)*t,\ y = y_1 - (a/g)*t$ 。有人写成 $x = x_1 - (b/g)*t$ ，导致代入后不成立。记住：x增加，y就要减少，保持等式平衡。
认为解只有一组
很多小学生第一次接触时，觉得找到一组解就完事了，实际上由于t可以取任意整数，有无限多解。比如6x+10y=2的解有(2,-1), (7,-4), (12,-7)……除非实际问题限制x和y是非负整数，才会是有限组。
忽略负数情况
当a或b是负数时，步长的符号需要根据实际情况调整。比如解 -3x+5y=2，gcd=1，通解中b/g=5，a/g=-3，那么公式中的符号要小心：x = x1 + 5*t, y = y1 - (-3)*t = y1+3t。最好统一把所有系数转为非负数再处理。

完整可运行的代码（带注释和验证循环）

下面给出C++和Python两个版本，代码已经在原有基础上增加了注释和验证循环，可以输出前几组解，方便你直观感受通解的样子。

C++ 版本

#include <iostream>
using namespace std;

// 扩展欧几里得，返回 gcd，并把一组特解存入 x 和 y (满足 ax+by=gcd)
int exgcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int x1, y1;          // 用于递归接收下一层的解
    int g = exgcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

// 求解 ax + by = c
// 如果无解，返回 false；否则输出通解公式，并返回 true
bool solve_linear(int a, int b, int c, int &x, int &y) {
    int g = exgcd(a, b, x, y);   // 先求 ax+by=g 的一组特解
    if (c % g != 0) {
        return false;            // 无解
    }
    int k = c / g;
    x *= k;                      // 得到原方程的一组特解
    y *= k;

    int step_x = b / g;          // 通解中 x 的步长
    int step_y = a / g;          // 通解中 y 的步长（注意符号）

    cout << "通解公式：" << endl;
    cout << "x = " << x << " + " << step_x << " * t" << endl;
    cout << "y = " << y << " - " << step_y << " * t" << endl;
    cout << "其中 t 是任意整数" << endl;

    // 验证：输出 t = -3 到 3 的几组解，让你看看规律
    cout << "\n验证前几个整数解：" << endl;
    for (int t = -3; t <= 3; t++) {
        int xt = x + step_x * t;
        int yt = y - step_y * t;
        int result = a * xt + b * yt;
        cout << "t = " << t << " : (" << xt << ", " << yt << ")  =>  ";
        cout << a << "*" << xt << " + " << b << "*" << yt << " = " << result;
        if (result == c) {
            cout << " ✓ 正确" << endl;
        } else {
            cout << " ✗ 错误！" << endl;   // 正常情况下不会出现
        }
    }
    return true;
}

int main() {
    int a, b, c;
    cout << "请输入方程系数 a, b, c (ax + by = c): ";
    cin >> a >> b >> c;

    int x, y;
    if (solve_linear(a, b, c, x, y)) {
        cout << "\n一组特解：x = " << x << ", y = " << y << endl;
    } else {
        cout << "方程无整数解。" << endl;
    }
    return 0;
}

Python 版本

def exgcd(a, b):
    """返回 (gcd, x, y) 使得 a*x + b*y = gcd"""
    if b == 0:
        return a, 1, 0
    g, x1, y1 = exgcd(b, a % b)
    x = y1
    y = x1 - (a // b) * y1
    return g, x, y

def solve_linear(a, b, c):
    """求解 ax+by=c，输出通解并验证"""
    g, x0, y0 = exgcd(a, b)
    if c % g != 0:
        print("方程无整数解。")
        return False

    k = c // g
    x = x0 * k          # 特解
    y = y0 * k
    step_x = b // g
    step_y = a // g

    print(f"通解公式：")
    print(f"x = {x} + {step_x} * t")
    print(f"y = {y} - {step_y} * t")
    print("其中 t 是任意整数")

    # 验证 t 从 -3 到 3
    print("\n验证前几个整数解：")
    for t in range(-3, 4):
        xt = x + step_x * t
        yt = y - step_y * t
        result = a * xt + b * yt
        mark = "✓" if result == c else "✗"
        print(f"t = {t:2d} : ({xt:3d}, {yt:3d})  =>  {a}*{xt} + {b}*{yt} = {result} {mark}")

    return True

# 测试
print("===== 测试1: 6x + 10y = 2 =====")
solve_linear(6, 10, 2)

print("\n===== 测试2: 3x + 5y = 14 =====")
solve_linear(3, 5, 14)

print("\n===== 测试3: 6x + 10y = 3 (无解) =====")
solve_linear(6, 10, 3)

运行结果会清晰展示通解的样子，并且通过验证让你放心：不管t怎么变，方程都成立。

怎么求非负整数解？（生活中最常用）

在实际生活中，我们往往要求x和y都是非负整数（因为硬币不能是负的）。这时候就需要在通解的基础上，找到所有t使得x≥0且y≥0。方法很简单：

写出不等式组： $x_1 + \frac{b}{g}t \ge 0 \quad \text{且} \quad y_1 - \frac{a}{g}t \ge 0$
解出t的范围： $t \ge \left\lceil -\frac{x_1 \cdot g}{b} \right\rceil \quad \text{且} \quad t \le \left\lfloor \frac{y_1 \cdot g}{a} \right\rfloor$
这个范围内的整数t就是所有非负整数解。

比如6x+10y=2，特解(2,-1)，步长step_x=5，step_y=3。不等式：

x=2+5t ≥ 0 => t ≥ -0.4 => t ≥ 0（取整）
y=-1-3t ≥ 0 => t ≤ -0.333... => t ≤ -1（取整）同时满足t≥0且t≤-1的整数不存在，所以没有非负整数解。这也符合直觉：6元和10元硬币凑不出2元，除非用负数。

二元一次不定方程求解