在上篇博文中，介绍了如何求出 \(ax+by=gcd(a,b)\) 的其中一组特解。

现在考虑该如何求出通解，即如何通过一个公式，能得到 \(x,y\) 的所有取值可能。

\(\texttt{例题}\)

luogu P5656

\(\texttt{思路}\)

现在，我们已经通过 \(\text{exgcd}\) 求出了一组特解 \(x,y\)，记为 \(x_0,y_0\)。

对于这一组特解，另一组解一定能写成 \((x_0+p),(y_0+q)\) 的形式。其中，\(q,p\) 为任意整数。

那么就有

解得：

因为 \(x,y\) 必须是整数，所以 \(p,q\) 也必须是正整数。

进而得到 \(ap\) 一定要是 \(b\) 的倍数。

将 \(\frac{a}{b}\) 化为 \(\frac{a/gcd(a,b)}{b/gcd(a,b)}\)，此时有分子分母互质，因此， \(q\) 必须是 \(b/gcd(a,b)\) 的倍数。

同理得 \(p\) 必须是 \(a/gcd(a,b)\) 的倍数。

于是得到了通解：

其中，\(t,k\) 为任意整数。

\(\texttt{插曲}\)

在例题 \(\text{Luogu P5656}\) 中，有这样一段话：

若该行对应的询问有整数解但无正整数解....

也就是说，我们还要判断， \(x,y\) 能不能同时为整数。

因为 \(a,b>0\)，所以当 \(x\) 取最小正整数值的时候，\(y\) 取到的值一定是在 \(x\leq0\) 的情况下的最大值。

因此，按照贪心的思路，求出在 \(x\) 取最小正整数值时 \(y\) 的值，并判断 \(y\) 的正负就可以了。

因此也可以得到，在 \(x,y>0\) 的情况下，\(x\) 或 \(y\) 的最大正整数值，是当另一个取到最小正整数值时的值。

\(\texttt{代码}\)

这道题的细节很多，结合代码来看一下。

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
	register int x=0;
	register char c=getchar();
	for(;!(c>='0'&&c<='9');c=getchar());
	for(;c>='0'&&c<='9';c=getchar())
		x=(x<<1)+(x<<3)+c-'0';
	return x;
}
struct p
{
	int x,y,gcd;
}ans;
p exgcd(int a,int b)
{
	p M;
	if(b==0)
	{
		M.x=1,M.y=0,M.gcd=a;
		return M;
	}
	M=exgcd(b,a%b);
	p Ans;
	Ans.x=M.y;
	Ans.y=M.x-(a/b)*M.y;
	Ans.gcd=M.gcd;
	return Ans;
}
int t;
int a,b,c;
void Mod(int &x,int mod)
{
	x=(x%mod+mod)%mod;
	if(!x) x+=mod;
}
signed main()
{
	cin>>t;
	register int x,y,s;
	while(t--)
	{
		a=read(),b=read(),c=read();
		ans=exgcd(a,b),s=ans.gcd;
		x=ans.x,y=ans.y;
		if(c%s!=0)//根据裴蜀定理处理无解情况
		{
			cout<<-1<<endl;
			continue;
		}
		c/=s,a/=s,b/=s;
                //在上方可以发现，p,q的值都是若干倍的a(或者b)/gcd(a,b)，为了方便，可以先把a,b,c都除以gcd(a,b)，以便后续处理。
		x*=c,y*=c;//求出特解(exgcd求的是 ax+by=gcd(a,b) 的特解，不是ax+by=c的)
                //注意，这里乘c是因为在上一行的化简之后a,b是互质的，因此gcd(a,b)=1,c是gcd(a,b)的c倍。
		Mod(x,b);//求出x最小正整数值
		if((c-a*x)/b>0)//根据贪心的思想，如果此时y还是正整数，那么就有正整数解
		{
			y=(c-a*x)/b;//求出此时y的值
			cout<<(int)ceil(y*1.0/a)<<" ";
                        //y每次变小就变小a，所以，y的正整数值的数量就是y/a向上取整。
                        //由于此处y不断变小，且x一直是正整数，所以y的正整数值的数量就是原方程正整数解的数量
			Mod(y,a),Mod(x,b);//取x,y的最小正整数值
			cout<<x<<" "<<y<<" ";
			x=(c-b*y)/a;//求x的最大正整数值
		        cout<<x<<" ";
		        Mod(x,b);
			y=(c-a*x)/b;//求y的最大正整数值
		        cout<<y<<endl;
		}
		else
		{
			Mod(x,b),Mod(y,a);//求x,y的最小正整数值并输出
			cout<<x<<" "<<y<<endl;
		}
	}	
	return 0;
}