【学习笔记】二元一次不定方程(exgcd)

定义

二元一次不定方程的形式为:ax+by=c,与同余方程 ax\equiv c\pmod{b} 等价

扩展欧几里得算法(exgcd)

该算法用于求解形如 ax+by=\mathrm{gcd}(a,b) 的不定方程

b=0 时,\mathrm{gcd}(a,b)=a,显然 x=1,y=0 是方程的一个特解

b\ne 0 时,设 x_2,y_2 是方程 ax+by=\mathrm{gcd}(b,a\%b) 的一个特解,则:
\begin{cases} x_1=y_2\\ y_1=x_2-\lfloor a/b \rfloor y_2 \end{cases}
是原方程的一个特解。证明如下:
ax_1+by_1=\mathrm{gcd}(a,b)=\mathrm{gcd}(b,a\%b)=bx_2+(a\%b)y_2=ay_2+b(x_2-\lfloor a/b\rfloor y_2)
a,b 项系数相等即可得到,证毕。

求特解

裴蜀定理:方程 ax+by=c 有整数解的充要条件为:\mathrm{gcd}(a,b)|c

方便起见,设 g=\mathrm{gcd}(a,b),A=\frac{a}{g},B=\frac{b}{g},C=\frac{c}{g}

先用exgcd求出方程 ax+by=g 的一个特解 {x_0}',{y_0}'

对上面方程两边同除以 g 再乘 c,得到方程 a\cdot Cx+b\cdot Cy=c

这样就得到了原方程的一个特解:
\begin{cases} x_0=C{x_0}'\\ y_0=C{y_0}' \end{cases}

求通解

若求出了方程的一个特解 x_0,y_0,则通解为:
\begin{cases} x=x_0+Bt\\ y=y_0+At \end{cases}
其中 t 为任意整数

求最小非负整数解

非负整数解指 x,y 均为非负整数的解

若求出了方程的一个特解 x_0,y_0,有:
\begin{cases} x_{min}=(x_0\%B+B)\%B\\ y_{max}=(c-ax_{min})/b \end{cases}

\begin{cases} y_{min}=(y_0\%A+A)\%A\\ x_{max}=(c-by_{min})/a \end{cases}

y_{max}<0x_{max}<0,则方程不存在非负整数解

否则,x_{max},x_{min},y_{max},y_{min} 分别为 x,y 的最大(最小)非负整数值

求非负整数解的个数

若存在非负整数解,则非负整数解的个数为:(x_{max}-x_{min})/B+1(y_{max}-y_{min})/A+1

Code

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

#include <iostream>
#include <stdio.h>
#include <string.h>
#define int long long

using namespace std;

int T, a, b, c;

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

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

signed main() {
    scanf("%lld", &T);
    while (T--) {
        scanf("%lld%lld%lld", &a, &b, &c);
        int g = gcd(a, b);
        if (c % g) {
            printf("-1\n");
            continue;
        }
        int x, y;
        exgcd(a, b, x, y);
        int A = a / g, B = b / g, C = c / g;
        x *= C, y *= C;
        int xmin = (x % B + B) % B;
        if (!xmin) {
            xmin += B;
        }
        int ymax = (c - a * xmin) / b;
        int ymin = (y % A + A) % A;
        if (!ymin) {
            ymin += A;
        }
        int xmax = (c - b * ymin) / a;
        if (ymax <= 0) {
            printf("%lld %lld\n", xmin, ymin);
            continue;
        }
        int cnt = (xmax - xmin) / B + 1;
        printf("%lld %lld %lld %lld %lld\n", cnt, xmin, ymin, xmax, ymax);
    }
}
点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注