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

题意：给定不定方程
$ax+by=c$
若该方程无整数解，输出 $-1$。
若该方程有整数解，且有正整数解，则输出其正整数解的数量，所有正整数解中 $x$ 的最小值，所有正整数解中 $y$ 的最小值，所有正整数解中 $x$ 的最大值，以及所有正整数解中 $y$ 的最大值。
若方程有整数解，但没有正整数解，你需要输出所有整数解中 $x$ 的最小正整数值， $y$ 的最小正整数值。

正整数解即为 $x, y$ 均为正整数的解，$\boldsymbol{0}$ 不是正整数。
整数解即为 $x,y$ 均为整数的解。
$x$ 的最小正整数值即所有 $x$ 为正整数的整数解中 $x$ 的最小值，$y$ 同理。

$1\le a,b,c\le 10^9$

根据裴蜀定理，

对于 $x,y$ 的二元一次不定方程 $ax+by=c$ ，其有解的充要条件为 $\gcd(a,b) \mid c$

可知方程无解当且仅当 $\gcd(a,b) \nmid c$

那么有解的时候，我们可以用扩展欧几里德算法求出一组特解

即 $x^{\prime},y^{\prime}$ 满足

$ax^{\prime}+by^{\prime}=\gcd(a,b)$

考虑转化为原方程的一组特解。令 $d=\gcd(a,b)$

则特解 $x_0=x^{\prime}\times \dfrac{c}{d}，y_0 = y’ \times \dfrac{c}{d}$ 满足

$ax_0 + by_0 = c$

此时的 $x_0,y_0$ 就是一个平凡的解，考虑转化为更有价值的解

考虑增大 $x_0$ 为 $x_0+p$ ，则 $y_0$ 需减小至 $y_0-q$

故

$\begin{cases} a\times(x_0+p)+b\times(y_0-q) = c\\\\ ax_0 + b y_0 = c \end{cases}$

可得 $p =\dfrac{bq}{a}$

可以发现这样的解有无数个，我们只要找到一个最小正整数解即可（即 $p,q\in \mathbb{Z}_+$ 且 $p,q$ 尽可能小）

$\because a\mid bq,b\mid bq$

$\therefore (bq)_{\min}=\operatorname{lcm}(a,b) = \dfrac{ab}{\gcd(a,b)}$

即

$\begin{aligned}\begin{cases} p_{\min}&=\dfrac{b}{d}\\ \\ q_{\min}&=\dfrac{a}{d} \end{cases}\end{aligned}$

于是我们尝试将 $x_0$ 调至最小正整数（ $y_0$ 同时也会改变）

即找到一个最小的整数 $k$ 使得 $x_0 + kp \ge 1$

则

$k= \left\lceil{\dfrac{1-x_0}{p}}\right\rceil$

然后将 $x_0$ 变为 $x_0 + kp$ 即可，此时 $y_0$ 变化为 $y_0-qk$

若此时 $y_0 > 0$ ，则存在正整数解

正整数解的个数：使 $y_0$ 不停地减 $q$ 就是所有可行正整数解，故答案为 $\left\lfloor{\dfrac{y_0-1}{q}}\right\rfloor+1$
$x$ 的最小正整数值：$x_0$
$y$ 的最小正整数值：使 $y$ 不停地减 $q$ ，最小的那个正整数就是答案，即 $(y_0-1)\bmod q + 1$
$x$ 的最大正整数值：$y$ 最小时 $x$ 最大
$y$ 的最大正整数值： $y_0$

若此时 $y_0 \le 0$ ，则仅存在整数解

$x$ 的最小正整数值： $x_0$
$y$ 的最小正整数值：构造 $y_0+k’q \ge 1$ ，易知 $k^{\prime} = \left\lceil{\dfrac{1-y_0}{q}}\right\rceil$ ，故答案为 $y_0+q\times \left\lceil{\dfrac{1-y_0}{q}}\right\rceil$

据说要开 $\text{long long}$ ，~~反正我#define int long long丝毫不慌（逃~~

主要代码如下（省略了快读和多组数据）

#define int long long
int exgcd(int a,int b,int &x,int &y)
{
    int d=a;
    if(!b)x=1,y=0;
    else d=exgcd(b,a%b,y,x),y-=a/b*x;
    return d;
}
void solve()
{
    int a,b,c,x,y;
    read(a);read(b);read(c);
    int d=exgcd(a,b,x,y);
    if(c%d!=0){puts("-1");return;}
    x*=c/d;y*=c/d;
    int p=b/d,q=a/d,k;
    k=ceil((1.0-x)/p),x+=p*k,y-=q*k;
    if(y>0)
    {
        write((y-1)/q+1);  pc(' ');
        write(x);          pc(' ');
        write((y-1)%q+1);  pc(' ');
        write(x+(y-1)/q*p);pc(' ');
        write(y);          pc(' ');
    }else
    {
        write(x);                       pc(' ');
        write(y+q*(int)ceil((1.0-y)/q));pc(' ');
    }
    pc('\n');
}