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

· · 题解

参考资料

题意简述

给定 1\le a,b,c\le 10^9，求解不定方程：

ax+by=c

基础知识

一次不定方程

一次不定方程（Linear Diophantine Equation）是形如以下形式的方程：

a_1x_1+a_2x_2+\dots+a_nx_n=b

其中 a_i 和 b 都是整数，我们会研究 x_i 的整数解。

特别地，当 n=2 时为二元一次不定方程：

a_1x_1+a_2x_2=b

我们可以调整一下变量名：

ax+by=c

裴蜀定理

裴蜀定理（Bézout's Lemma）给出了二元一次不定方程 有整数解 的充要条件。

对于整数 a,b（不全为 0），存在整数 x,y 使得 ax+by=\gcd(a,b)。

换句话说，ax+by=c 有整数解当且仅当 \gcd(a,b)\mid c。

证明详见 Bézout's identity - Wikipedia。

欧几里得算法

欧几里得算法（辗转相除法）可以求两个整数的 最大公约数（Greatest Common Divisor，GCD）。

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

证明：设 a=kb+c。若 d\mid a,b，则 d\mid c；若 d\mid b,c，则 d\mid a。故 a,b 与 b,c 的公约数集合相同，因此 \gcd(a,b)=\gcd(b,c)=\gcd(b,a\bmod b)。

显然 a\bmod b<b，因此可以递归求解。特别地，\gcd(a,0)=a。

\gcd(a,b)= \begin{cases} a & b=0 \\ \gcd(b,a\bmod b) & \text{otherwise} \end{cases} 
ll Gcd(ll a,ll b)
{
    return !b?a:Gcd(b,a%b);
}

扩展欧几里得算法

扩展欧几里得算法（Extended Euclidean Algorithm，EXGCD）可以求 ax+by=\gcd(a,b) 的 一组整数解。

ax+by=\gcd(a,b)\iff ay+b\left(x-\left\lfloor\frac{a}{b}\right\rfloor y\right)=\gcd(a,b)

设一组整数解为 (x_0,y_0)：

ax_0+by_0=\gcd(a,b) bx_1+(a\bmod b)y_1=\gcd(b,a\bmod b)

根据欧几里得算法：

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

所以：

ax_0+by_0=bx_1+(a\bmod b)y_1

又因为：

a\bmod b=a-\left\lfloor\frac{a}{b}\right\rfloor\times b

所以：

ax_0+by_0=bx_1+\left(a-\left\lfloor\frac{a}{b}\right\rfloor\times b\right)y_1 ax_0+by_0=ay_1+bx_1-\left\lfloor\frac{a}{b}\right\rfloor\times by_1=ay_1+b\left(x_1-\left\lfloor\frac{a}{b}\right\rfloor y_1\right)

所以：

x_0=y_1,y_0=x_1-\left\lfloor\frac{a}{b}\right\rfloor y_1

将 x_1,y_1 不断代入递归求解直至 \gcd 为 0 递归 x=1,y=0 回去求解。

tuple<ll,ll,ll> exgcd(ll a,ll b)
{
    if(!b)return {a,1,0};
    auto [g,x,y]=exgcd(b,a%b);
    return {g,y,x-a/b*y};
}

解题思路

我们先用 扩展欧几里得算法 求出最大公约数 g=\gcd(a,b) 和一组整数解 (x_0,y_0)。

ax_0+by_0=g

根据裴蜀定理，当 c 不是 g 的倍数时无解，输出 -1。

将方程两边同时乘以 \frac{c}{g}：

\frac{c}{g}\cdot ax_0+\frac{c}{g}\cdot by_0=\frac{c}{g}\cdot d=c

此时我们令 x_0\gets\frac{c}{g}\cdot x_0,y_0\gets\frac{c}{g}\cdot y_0，就得到了原问题的一组解 (x_0,y_0)。

每两组解的 x 和 y 分别相差了：

d_x=\frac{b}{g},d_y=\frac{a}{g}

而所有正整数解分别为：

(x_{\min},y_{\max}),(x_{\min}+d_x,y_{\max}-d_y),\dots,(x_{\max},y_{\min})

显然 x_{\min}\in[1,d_x],y_{\min}\in[1,d_y]，可以通过取模得到：

x_{\min}=(x_0-1)\bmod d_x+1,y_{\min}=(y_0-1)\bmod d_y+1

当 x 最小时 y 最大，y 最小时 x 最大，因此：

x_{\max}=\frac{c-by_{\min}}{a},y_{\max}=\frac{c-ax_{\min}}{b}

因此正整数解的数量为：

n=\frac{x_{\max}-x_{\min}}{d_x}+1=\frac{y_{\max}-y_{\min}}{d_y}+1

参考代码

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

using ll=long long;
tuple<ll,ll,ll> exgcd(ll a,ll b)
{
    if(!b)return {a,1,0};
    auto [g,x,y]=exgcd(b,a%b);
    return {g,y,x-a/b*y};
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--)
    {
        ll a,b,c;
        cin>>a>>b>>c;
        auto [g,x,y]=exgcd(a,b);
        if(c%g){cout<<-1<<'\n';continue;}
        x*=c/g;y*=c/g;
        ll dx=b/g,dy=a/g;
        ll x_min=(x%dx+dx-1)%dx+1,y_min=(y%dy+dy-1)%dy+1,x_max=(c-b*y_min)/a,y_max=(c-a*x_min)/b;
        if(y_max>0)cout<<(x_max-x_min)/dx+1<<' '<<x_min<<' '<<y_min<<' '<<x_max<<' '<<y_max<<'\n';
        else cout<<x_min<<' '<<y_min<<'\n';
    }
    return 0;
}