imicola 线性丢番图方程
线性丢番图方程

线性丢番图方程

502 字 · 约 1 分钟

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

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

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

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

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

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

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

其具体作用为,在确定线性丢潘图方程有解的情况,可以使用扩展欧几里得算法展欧几里得算法找出其中一个特解(x0,y0)(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;
}
cpp

知识关联

1 反向链接 · 1 提及笔记
局部关系图谱 悬停高亮 · 点击跳转