二元一次不定方程（exgcd）

前置知识

扩展欧几里得算法（辗转相除法）

对 $\forall a,b \in \mathbb{N^+}$，有

$\gcd(a,b)=\gcd(b, a\bmod b)$

裴蜀定理

对 $\forall a,b\in \mathbb{N^+}$，$\exists x,y\in \mathbb{Z}$，使得

$ax+by=\gcd(a,b)$

问题引入

给定不定方程

$ax+by=\gcd(a,b)$

求出 $x,y$ 的一组解。

解法：我们令

$by'+(a\bmod b)x'=\gcd(b, a\bmod b)$

又因为

$a\bmod b=a-\lfloor \dfrac{a}{b} \rfloor b$

代入得

$ax'+b(y'-\lfloor \dfrac{a}{b} \rfloor x')=\gcd(b,a\bmod b)$

由 $\gcd(a,b)=\gcd(b, a\bmod b)$，得

$\left\{ \begin{aligned} x&=x'\\ y&=y'-\lfloor \dfrac{a}{b} \rfloor x' \end{aligned} \right.$

由于在辗转相除法的最后，必定是 $a'=\gcd(a,b),b'=0$，则此时 $x'=1,y'=0$。那么我们可以在递归回溯的时候逐层求出所求 $x,y$，得到如下代码：

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

注意 $x,y$ 为传址调用。

现在考虑新的问题：等式右边 $\gcd(a,b)$ 被替换为正整数 $c$，求解的数量、$x,y$ 的最大最小值。

把上文代码求得的 $x,y$ 分别乘上 $\dfrac{c}{\gcd(a,b)}$ 即为方程的一组解。

引理 1：$\gcd(a,b) | c$ 是 $ax+by=c$ 有整数解的充分必要条件。

证明：设 $d=\gcd(a,b)$，$a=k_1d$，$b=k_2d$，则 $k_1x+k_2y=\dfrac{c}{d}$。左边是整数，因此 $\dfrac{c}{d}\in \mathbb{Z}$，即 $d | c$，充分性得证。由 $k_1,k_2$ 互质，所以 $k_1x'+k_2y'=1$ 一定有整数解。由 $\dfrac{c}{d}\in \mathbb{Z}$，得原方程的一组解为

$\left\{ \begin{aligned} x&=x'\dfrac{c}{d}\\ y&=y'\dfrac{c}{d} \end{aligned} \right.$

必要性得证。

由此我们得到了判断该方程是否有解的方法。

引理 2：设 $x_0,y_0$ 为 $ax+by=c$ 的解，那么所有的解都可表示为

$\left\{ \begin{aligned} x&=x_0+k_2t\\ y&=y_0-k_1t (t\in \mathbb{Z}) \end{aligned} \right.$

把 $x,y$ 代入方程，容易验证。

上式变换后，可知当

$\lceil \dfrac{-x_0+1}{k_2} \rceil \le t \le \lfloor \dfrac{y_0-1}{k_1} \rfloor$

时，$x,y$ 均为正整数。

若 $\lceil \dfrac{-x_0+1}{k_2} \rceil > \lfloor \dfrac{y_0-1}{k_1} \rfloor$，则原不定方程无正整数解。

显然 $x$ 越大，$y$ 越小，反之亦然。且正整数解的个数为 $\max\{0,\lfloor \dfrac{y_0-1}{k_1} \rfloor-\lceil \dfrac{-x_0+1}{k_2} \rceil+1\}$。

题目应用

到这里我们就可以解决下面这些题了。

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

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll T, a, b, c, d, t, cnt;

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

void solve()
{
    ll x, y, l, r;
    scanf("%lld%lld%lld", &a, &b, &c);
    d = __gcd(a, b);
    if (c % d) {
        printf("-1\n");
        return;
    }
    exgcd(a, b, x, y);
    x *= c / d; y *= c / d;
    a /= d; b /= d;
    l = ceil((1.0 - double(x)) / (double)b);
    r = floor(((double)y - 1.0) / (double)a);
    if (l <= r)
        printf("%lld %lld %lld %lld %lld\n", r - l + 1, x + b * l, y - a * r, (c - b * d * (y - a * r)) / (a * d), (c - a * d * (x + b * l)) / (b * d));
    else
        printf("%lld %lld\n", x + b * l, y - a * r);
}

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

[NOIP2012 提高组] 同余方程

同余方程 $ax\equiv c \pmod b$ 其实就是 $ax+by=c$。答案为 $x$ 的最小正整数解。