贝祖定理：
即如果a、b是整数，那么一定存在整数x、y使得ax+by=gcd(a,b)。
换句话说，如果ax+by=m有解，那么m一定是gcd(a,b)的若干倍。（可以来判断一个这样的式子有没有解）
有一个直接的应用就是 如果ax+by=1有解，那么gcd(a,b)=1；
int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
然而这并不能告诉我们x,y解是多少。
扩欧
首先我们观察上面的式子发现一定有一个解a*1+b*0=gcd(a,b)。（b%a=0）
但是这个ab并不是我们想要的。不过我们可以倒推，原式即：
b*x1+(a%b)*y1=gcd
我们知道：a%b=a-(a/b)*b；带入：
b*x1 + (a-(a/b)*b)*y1
= b*x1 + a*y1 – (a/b)*b*y1
= a*y1 + b*(x1 – a/b*y1) = gcd
发现 x = y1 , y = x1 – a/b*y1
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
ll exgcd(ll a,ll b,ll &x,ll &y)//这个是返回值版的
{
if(!b)
{
x=1;y=0;
return a; //边界
}
int r=exgcd(b,a%b,x,y);
int temp=y; //把x y变成上一层的
y=x-(a/b)*y;
x=temp; //更改x和y的值，因为是引用的
return r; //得到a b的最大公因数
}
void exgcd1(ll a,ll b,ll &d,ll &x,ll &y)//这个不返回直接更新
{
if(!b)d=a,x=1,y=0;
else
{
exgcd1(b,a%b,d,y,x);
y-=x*(a/b);
}
}
int main()
{
ll a,b,d,x,y;
cin>>a>>b;
d=exgcd(a,b,x,y);//最大公约数
// exgcd1(a,b,d,x,y);
printf("%d %d",x,y);//x，y已经被更新了
return 0;
}
解释一下exgcd1的递推式。
d是最大公约数，这个在b=0，即上一层a%b=0时找到最大公约数，更新传回即可。
我们x和y都是直接更新地址的，那我们这里的y其实就是传给上一层的x，相当于y=x-(a/b)*y,
因为我们传下来的时候是将x和y颠倒的，那么这里x就和y互换,即y-=(a/b)*x，x还是x，传上去就变成y了。
x即为a%b意义下的逆元。
注意，一个数mod一个数是有可能没有逆元的，这时候x好像是返回1。moreover，如果是有逆元的，解出来的x有可能是负数，这时候你可能需要x=(x+mod)%mod.
求不定方程
（我之前没用Markdown写得真难受）
（这个部分是我学了excrt之后才更新的）
（之前学的真是肤浅而且一团乱麻）
exgcd既然可以求ax+by=gcd的解，那么一定就可以求ax+by=c的解。
假设gcd=gcd(a,b)，那么我们先把方程两边同时乘gcd/c，那么是不是就可以求x和y了呢？那么求完之后我们在给他乘回去不就行了？
那就行了。
判断无解的情况：如果求出来的gcd并不能被c整除，说明在数论范围内它无解。
鉴于不定方程的性质，x的最小正整数解是在b意义下取模的，y的最小正整数解是在a意义下取模的。我们就可以求出x，y的最小整数解和整数解的个数。因为x和y的增减性是相反的，我们也就可以相应算出最大值。
#include<bits/stdc++.h>
#define int long long //watch out!
using namespace std;
inline int read()
{
int x=0,w=0;char c=getchar();
while(!isdigit(c))w|=c=='-',c=getchar();
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
return w?-x:x;
}
inline void write(int x)
{
if(x>9)write(x/10);
putchar(x%10+'0');
}
inline void exgcd(int a,int b,int& d,int& x,int& y){
if(!b)d=a,x=1,y=0;
else exgcd(b,a%b,d,y,x),y-=(a/b)*x;
}
inline void solve(int a,int b,int c)
{
int cnt=0,miny,maxy,minx,maxx;
int gcd,x,y;
exgcd(a,b,gcd,x,y);
if(c%gcd!=0){printf("-1\n");return;}
a/=gcd;b/=gcd;c/=gcd;//这里学习了一下大佬的做法，将所有答案除以gcd，实际上是一样的，不过下面的x和y就不是乘c/gcd了。
x*=c;
y*=c;
minx=x>0&&x%b!=0?x%b:x%b+b;
maxy=(c-minx*a)/b;
miny=y>0&&y%a!=0?y%a:y%a+a;
maxx=(c-miny*b)/a;
if(maxx>0)cnt=(maxx-minx)/b+1;
if(cnt==0)printf("%d %d\n",minx,miny);
else printf("%d %d %d %d %d\n",cnt,minx,miny,maxx,maxy);
}
signed main()
{
int t=read();
while(t--){
int a=read(),b=read(),c=read();
solve(a,b,c);
}
return 0;
}