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

Mirasycle · 2025-05-26 20:56:29 · 题解

扩展欧几里得算法是用于求解形如 ax+by=c 的方程，根据裴蜀定理其有解的充要条件是 \gcd(a,b) | c。

我们可以利用类似于求解 \gcd 的方法来算 exgcd。由于 \gcd(a,b)=\gcd(b,a\bmod b)，所以把系数替换成 (b,a\bmod b) 不仅保证有解，而且还缩小了问题规模，如果不断缩小问题规模直到边界条件就可以很轻松的得到一组解，而且根据辗转相除法，我们进行这个轮数为 O(\log V)。

我们现在计算 ax+by=d=\gcd(a,b)。假设我们已经知道了 bx'+(a\bmod b)y'=d 的解了，那么有

也就是 ay'+b(x'-\lfloor\dfrac{a}{b}\rfloor y')。

对比系数，x\gets y',y\gets x'-\lfloor\dfrac{a}{b}\rfloor y'。

按照上述流程递归求解即可。

临界条件是最后 a=d,b=1，此时解为 x=1,y=0。

最后解出 ax+by=d 后，将解 \times\dfrac{c}{d}，就可以得到一组特解 (x_0,y_0) 了。

exgcd 求出来的特解是满足 ax+by=d 的 \lvert x\rvert+\lvert y\rvert 最小的一组解，注意这里的必须是 =d 的解，如果是 =c 的话就不满足这个性质了！ 关于如何在 =c 的时候求出这个最小解，可以去看看 P3543。

有了特解之后，我们需要得到方程的特解。

设 x,y 的变化量为 \Delta x 和 \Delta y，有 a\Delta x+b\Delta y=0。得到 \Delta x=-\dfrac{b}{a}\Delta y=-\dfrac{b/d}{a/d}\Delta y（最后一步是约分）。

所以可以得到方程的通解为 \begin{cases} x=x_0+\dfrac{b}{d}k \\y=y_0-\dfrac{a}{d}k \end{cases}

得到通解的表达式之后就可以求一些特殊位置的解了。

令 A=\dfrac{a}{d},B=\dfrac{b}{d}，根据通解表达式可以得到 x\equiv x_0\pmod B，于是 x 的最小正整数解就是

对于 y 同理。

对于 x,y 都是正整数的情况下，显然是其中一个变大会让另一个变小，所以 x 的最小正整数解对应的是 x>0 的情况下 y 的最大值。注意特判掉此时 y 最大值 <0 的情况。

关于 x,y>0 的解的个数，由于 x 每次变化 B，那么就是 \dfrac{x_{\max}-x_{\min}}{B}+1 了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void exgcd(int a,int b,ll& x,ll& y){
    if(!b){ x=1; y=0; return ; }
    exgcd(b,a%b,y,x); y-=a/b*x;
}
void solve(){
    int a,b,c; cin>>a>>b>>c; int d=__gcd(a,b);
    if(c%d){ cout<<"-1\n"; return ; }
    ll x0=0,y0=0; exgcd(a,b,x0,y0);
    x0*=c/d; y0*=c/d;//特解 
    ll xmn=x0%(b/d),ymn=y0%(a/d);
    xmn=xmn<=0?xmn+b/d:xmn;
    ymn=ymn<=0?ymn+a/d:ymn;
    ll xmx=(c-b*ymn)/a,ymx=(c-a*xmn)/b;
    if(ymx<=0){ cout<<xmn<<" "<<ymn<<"\n"; return ; }
    cout<<(xmx-xmn)/(b/d)+1<<" "<<xmn<<" "<<ymn<<" "<<xmx<<" "<<ymx<<"\n";
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T; cin>>T;
    while(T--) solve();
    return 0;
}