扩展欧几里得 解二元一次方程组

扩展欧几里得: 最大公约数 - OI Wiki (oi-wiki.org) 

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

P5656 【模板】二元一次不定方程 (exgcd) - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10,mod=1e9+7;
int a,b,x,y;
int exgcd(int a,int b,int &x,int &y){
    if(!b){
        x=1,y=0;
        return a;
    }
    int d=exgcd(b,a%b,y,x);
    int tmp=x;
    x=y;
    y=tmp-(a/b)*y;
    return d;
}
void solve(){
    int a,b,c; cin>>a>>b>>c;
    int d=exgcd(a,b,x,y);
    if(c%d) return cout<<-1<<'\n',void();
    x=x*c/d,y=y*c/d;
    int p=b/d,q=a/d,k;
    if(x<0) k=ceil((1.0-x)/p),x+=p*k,y-=q*k;
    else k=(x-1)/p,x-=p*k,y+=q*k;
    if(y>0)
        cout<<(y-1)/q+1<<' '<<x<<' '<<(y-1)%q+1<<' '<<x+(y-1)/q*p<<' '<<y<<'\n';
    else 
        cout<<x<<' '<<y+q*(int)ceil((1.0-y)/q)<<'\n';
}
signed main(){
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int t;cin>>t;while(t--)solve();
}