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

· · 题解

解析

由裴蜀定理可知一定有一组 x,y 使 ax + by = gcd(a, b) 成立，而对于 ax + by = c，c 必须是 gcd(a, b) 的倍数该方程才会有解，否则无解（裴蜀定理还不会的点这里裴蜀定理）。

恭喜你已经会了第一步，成功的掌握了前置知识，现在我们继续研究，先从求解 ax + by = gcd(a, b) 入手吧！

相信聪明的你一定会辗转相除求 gcd 吧，我们来模拟一下这个过程，假设现在有 220 和 150 两个数：

第一轮：220 ~170 较小数不为零，继续 gcd(170, 220 \bmod 170)

第二轮：170 ~50 继续 gcd(50, 170 \bmod 50)

第三轮：50 ~20 继续 gcd(20, 50 \bmod 20)

第四轮：20 ~10 继续gcd(10, 20 \bmod 10)

第五轮：10 ~0 较小数为零了，返回。

我们回头再看每一轮的操作，假设现在的第一个数为 x_0，第二个数为 y_0，现在即将生成下一轮的两个数 x_1,y_1。

好吧，其实 $y_1 = x_0 - y_0 \times \lfloor\frac{x_0}{y_0}\rfloor$。 因此，我们可以不断用 $x$ 去代换 $x'$，用 $y$ 取代换 $y'$，最后 gcd$(a, b)$ 就可以用 $ax + by$ 来表示了，方程得解。 大功告成，现在我们已经成功得到了一组解 $x_0$ 和 $y_0$，回到 $ax + by = c$ 中，则 $x = x_0 \times \frac{c } {\gcd(a, b)}$，$y = y_0 \times \frac{c } {\gcd(a, b)}$，然后将等式两边同时除以 gcd$(a,b)$。 得到$a'x + b'y = c'

现在假设存在另外一组 x' 和 y' 使等式成立，则我们可以这样表示 x' 和 y' ：

x' = x + kb'\\ y' = y - ka'

考虑 x_{min}，则 x + kb' \ge 1，可得 k \ge (1 - x) / b'，那么 x_{min} = x + b' \cdot \lceil\frac{(1 - x)}{b}\rceil，y_{min} 同理可得。

再考虑 x_{max}，因为 x 和 y 肯定是你增我减才能使等式依然成立，则 y_{min} 时取到 x_{max}，x_{min} 时取到 x_{max}。

那么解的个数是多少呢？ 因为 y 最大值与最小值之间每 b 个数就有一个解，所以个数为 \frac{y_{max} - y_{min}} {a}+ 1 个。

最后一步，判定是否无正整数解，不难发现，若 x 取最小值时， y_{max} \le 0 那么 y_{max} 肯定无法更大了，因此可以判定为无解。

最后代码奉上：

#include <bits/stdc++.h>
#define int long long
#define double long double
using namespace std;

int aa, bb, cc, ans = 0, jx = 0, jy = 0;
int x, y = 0;
void exgcd(int a, int b, int xa, int ya, int xb, int yb){//求一组特殊解 
    if(b == 0){
        ans = a;
        jx = -xa;
        jy = -ya;
        return ;
    }
    else{
        int k = a / b;
        exgcd(b, a % b, xb, yb, xa - k * xb, ya - k * yb);
    }
}
signed main()
{
    int T = 0;
    cin >> T;
    for(int t = 1; t <= T; t++){
        cin >> aa >> bb >> cc;
        exgcd(aa, bb, -1, 0, 0, -1);
        if(cc % ans != 0){//判定无解 
            cout << -1 << endl;
            continue;
        }
        aa = aa / ans;//化为最简式 
        bb = bb / ans;
        cc = cc / ans;
        jx = jx * cc;
        jy = jy * cc;
        double ka = ceil((1.0 - jx) / bb);
        int xmin = jx + bb * ka;
        double kb = floor((jy - 1.0) / aa);
        int ymin = jy - aa * kb;
        int xmax = (cc - bb * ymin) / aa;
        int ymax = (cc - aa * xmin) / bb;
        if(xmax <= 0){//判定无正整数解 
            cout << xmin << ' ' << ymin << endl;
            continue;
        }
        else{
            cout << (ymax - 1) / aa + 1 << ' ' << xmin << ' ' << ymin << ' ' << xmax << ' ' << ymax << endl;        
        }   
    } 
    return 0;
}

本人第一次写题解，管理大大求过 QwQ。

具体哪里有错说一下吧QwQ