基本知識

擴展歐幾里德算法即 exgcd，一般用來求形如 \(ax+by=\gcd(a,b)\) 的二元一次不定方程的整數解。以下為了方便將用 \(d\) 代替 \(\gcd(a,b)\)。

考慮 \(\gcd(b,a\bmod b)=\gcd(a,b)\)，，于是遞歸，邊界是 \(b=0\)，此時方程是 \(ax=a\)，顯然 \(x=1\)，\(y\) 沒有限制。

再考慮 \(bx+(a\bmod b)y=d\) 的解如何轉變成 \(ax+by=d\) 的，我們設 \(bx+(a\bmod b)y=d\) 的解 \(x=y_0,y=x_0\)，于是 \((a\bmod b)x_0+by_0=d\)，因此我們可以令 \(ax+by=d\) 的解 \(x=x_0\)，注意到 \(a=b\times\lfloor \frac{a}{b}\rfloor+a\bmod b\)，因此 \(ax+by=d\) 和 \((a\bmod b)x_0+by_0=d\) 兩式相減得 \(b\times\lfloor \frac{a}{b}\rfloor x_0+b(y-y_0)=0\)，變一下形得 \(y=y_0-\lfloor \frac{a}{b}\rfloor x_0\)。

這樣的話，代碼就不難寫了：

ll exgcd(ll a,ll b,ll &x,ll &y){
    if(!b){
        x=1;y=0;
        return a;
    }ll d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}

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

考慮 exgcd，后面將用 \(d\) 表示 \(\gcd(a,b)\)。

首先用 exgcd 求 \(ax+by=d\) 一組解 \(x_0,y_0\)。考慮根據裴蜀定理，如果 \(c\) 不是 \(d\) 的倍數，則必定無解。于是對于 \(ax+by=c\)，我們得到了一組解 \(\begin{cases}x_1=x_0\times \frac{c}w0obha2h00\\y_1=y_0\times\frac{c}w0obha2h00\end{cases}\)。

接下來求通解，令 \(a(x_1+n)+b(y_1+m)=c\)，拆開后得 \(ax_1+by_1+an+bm=c\)，注意到 \(ax_1+by_1=c\)，于是 \(an+bm=0\)。由于 \(a,n,b,m\) 都是整數，因此絕對值最小的 \(n,m\) 當然是湊 \(a,b\) 的最小公倍數（也就是 \(\frac{ab}w0obha2h00\)），也就是使得 \(an+bm=\frac{ab}w0obha2h00-\frac{ab}w0obha2h00=0\)，因此 \(n=\frac{b}w0obha2h00,m=\frac{a}w0obha2h00\)。這里為了方便辨識，令 \(tx=n,ty=m\)。于是通解出來了：

其中，\(k\in \mathbb{Z}\)。

這樣，后面的就好求了。我們先求 \(x\) 的最小正整數解，此時有 \(x_{\max}+k\times tx\ge 1\)，變一下形得 \(k\ge\lceil\frac{1-x_{\max}}{tx}\rceil\)，同時，由于 \(x\) 達到了最小，那 \(y\) 就達到了最大，如果這時的 \(y_{\max}\) 仍不為正，那么就無正整數解，其中 \(y\) 的最小正整數解也能用同樣的方法求出。

如果有正整數解，我們考慮這個最大的 \(y_{\max}\)，設最小的為 \(y_{\min}\)，則 \(y_{\min}=y_{\max}-k\times ty\ge 1\)，得 \(k\le\lfloor\frac{y_{\max}-1}{ty}\rfloor\)，于是我們也得到解的數量為 \(\lfloor\frac{y_{\max}-1}{ty}\rfloor+1\)，同理也能求出 \(x_{\max}\)。

這樣代碼也不難寫了：

#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define int long long
typedef long long ll;
ll exgcd(ll a,ll b,ll &x,ll &y){
    if(!b){
        x=1;y=0;
        return a;
    }ll d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}
signed main(){
    cin.tie(0);ios::sync_with_stdio(0);
    int T;cin>>T;
    while(T--){
        ll a,b,c;cin>>a>>b>>c;int x,y;
        ll d=exgcd(a,b,x,y);
        if(c%d){
            cout<<"-1\n";continue;
        }
        x=x*(c/d),y=y*(c/d);
        ll tx=b/d,ty=a/d;
        ll k=ceil((1.0-x)/tx);
        x+=tx*k;y-=ty*k;
        if(y<=0){
            cout<<x<<' '<<y+ty*(long long)ceil((1.0-y)/ty)<<'\n';
        }else{
            cout<<(y-1)/ty+1<<' '<<x<<' '<<(y-1)%ty+1<<' '<<x+(y-1)/ty*tx<<' '<<y<<'\n';
        }
    }
    return 0;
}