拓展欧几里得定理（模板）

//laoshi牌题解，你值得拥有
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//解出来的x,y绝对值不会超过max(a,b)
//ax+by=d的整数解(x0,y0)
//x0是最小合法x,y0是最大合法y
//通解：x=x0+b't,y=y0-a't
//其中b'=b/gcd(a,b),a'=a/gcd(a,b)
ll gcd(ll a,ll b){
return b?gcd(b,a%b):a;
}
ll a,b,d,x,y;
bool exgcd(ll a,ll b,ll &x,ll &y,ll d){
//当前目的：求解ax+by=d这个方程
if(b=0){//a,b不断改变的过程中,最终必然会成为0
if(d%a=0){
x=d/a;
y=0;
return true;
}
return false;
}
ll temp_x,temp_y;
if(exgcd(b,a%b,temp_x,temp_y,d)){
x=temp_y;
y=temp_x-a/bx;
return true;
}
return false;
}
void solve(){
scanf("%lld %lld %lld",&a,&b,&d);
bool result=exgcd(a,b,x,y,d);
//无整数解
if(!result){
printf("-1\n");
return;
}
//x和y的变化量，x=x+kdx,y=y-kdy
ll dx=b/gcd(a,b),dy=a/gcd(a,b);
//x取最小正整数是的解(x0,y0)->y1为最大正整数解的y
ll k=x%dx<=0?x/dx-1:x/dx;
ll y0=y+kdy;
ll x0=x-kdx;
//y取最小正整数是的解(x1,y1)->x1为最大正整数解的x
k=y%dy<=0?y/dy-1:y/dy;
ll y1=y-kdy;
ll x1=x+k*dx;
if(y0<=0){
cout<<x0<<" "<<y1<<"\n";
return;
}
ll num=(x1-x0)/dx+1;
cout<<num<<" "<<x0<<" "<<y1<<" "<<x1<<" "<<y0<<"\n";
}
int main(){
int t;
cin>>t;
while(t--){
solve();
}
}
//太难了 根本听不懂
//这个代码费了一段时间