洛谷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');
}