线性丢番图方程

数学 丢番图 数论

20 线性丢潘图方程(Diophantine equation)

线性丢番图方程（Diophantine equation）通常指的是形如 $ax+by=c$的方程，其中 $a,b,c$ 是整数，而我们感兴趣的是找到整数解 $x,y$。

孩子们，牛客周赛77第三题会这个秒杀了（怪不得那群人可以20min ak，全是板子题）

$x,y$ 存在解的情况下，$a,b$ 满足以下条件

• c 必须是 a 和 b 的最大公约数 (gcd) 的倍数

具体而言，当 $c\mathrm{mod}(\gcd (a,b))=0$ 时存在$x,y$ 使上述方程存在整数解

• 扩展：
• 若上述条件满足，则存在无穷多组解 $(x,y)$ ,一旦找到一组特殊的解$(x_0,y_0)$，则所有解都可以被表示出来，其表示方式如下
  $x=x_0+k\left(\frac{b}{g}\right)$
  $y=y_0-k\left(\frac{a}{g}\right)$
• 其中$g=\gcd (a,b)$

其具体作用为，在确定线性丢潘图方程有解的情况，可以使用扩展欧几里得算法展欧几里得算法找出其中一个特解$(x_0,y_0)$ , 然后找出所有解的通项

找出丢潘图方程通项代码模板

需要用到扩展欧几里得算法进行实现

• 如下：

#include <bits/stdc++.h>
using namespace std;
 
// 扩展欧几里得算法
int exgcd(int a, int b, int &x, int &y)
{
    if (b == 0) {
        x = 1;
        y = 0;
        return a; // 返回gcd(a, b)
    }
    int r = exgcd(b, a % b, x, y);
    int t = y;
    y = x - (a / b) * y;
    x = t;
    return r;
}
 
int main()
{
    int a, b, c;
    cout << "请输入线性丢番图方程(ax+by=c)的系数a, b和常数c : " << endl;
    cin >> a >> b >> c;
    int g = __gcd(a, b); // 计算gcd(a, b)
    if (c % g != 0) {
        cout << "方程无整数解." << endl;
        return 0;
    }
    // 使用扩展欧几里得算法找到一个特解
    int x0, y0;
    exgcd(a / g, b / g, x0, y0);
    x0 *= c / g;
    y0 *= c / g;
    cout << "一个特解为: x = " << x0 << ", y = " << y0 << endl;
    // 输出一般解
    cout << "一般解的形式为:" << endl;
    cout << "x = " << x0 << " + " << b / g << " * k" << endl;
    cout << "y = " << y0 << " - " << a / g << " * k" << endl;
    cout << "其中k为任意整数." << endl;
    return 0;
}

Tip

由于 $g$ 已经是 $a$ 和 $b$ 的最大公约数，因此 $\frac{a}{g}$ 和 $\frac{b}{g}$ 互质（即它们的最大公约数为1）。这样做的目的是为了简化问题，使得新的系数 $\frac{a}{g}$ 和 $\frac{b}{g}$ 成为互质的整数，从而可以使用扩展欧几里得算法来求解简化后的方程。
因为有了简化过程，所以结果出来时要乘上 $\frac{c}{g}$来回复正常解