最大公约数（GCD）

参考资料

• 最大公约数 - OI Wiki
• 扩展欧几里得算法 - OI Wiki

欧几里得算法（辗转相除法）

$$\gcd{(a,b)}=\gcd{(b,a\bmod b)}$$

递归

int Gcd(int a,int b)
{
	return !b?a:Gcd(b,a%b);
}

迭代

ll Gcd(ll a,ll b)
{
	while(b)
	{
		ll tmp=a;
		a=b;
		b=tmp%b;
	}
	return a;
}

扩展欧几里得（EXGCD）

$$ax+by=\gcd{(a,b)}$$

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

例题

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

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

给定不定方程 $ax+by=c$。（$a,b,c\le 10^9$）

• 若无整数解，输出 -1。
• 若有正整数解，输出正整数解的数量，在正整数解中 $x$ 的最小值，$y$ 的最小值，$x$ 的最大值，$y$ 的最大值。
• 若没有正整数解，输出 $x$ 的最小正整数值，$y$ 的最小正整数值。

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
ll exgcd(ll a,ll b,ll &x,ll &y)
{
	if(b==0){x=1;y=0;return a;}
	ll d=exgcd(b,a%b,y,x);
	y-=a/b*x;
	return d;
}
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		ll a,b,c,x,y;
		cin>>a>>b>>c;
		ll d=exgcd(a,b,x,y);
		if(c%d){cout<<"-1"<<'\n';continue;}
		x*=c/d;y*=c/d;
		ll x1=b/d,y1=a/d;
		ll x_min=(x%x1+x1-1)%x1+1,y_min=(y%y1+y1-1)%y1+1;
		ll x_max=(c-b*y_min)/a,y_max=(c-a*x_min)/b;
		if(y_max<=0)cout<<x_min<<' '<<y_min<<'\n';
		else cout<<(x_max-x_min)/x1+1<<' '<<x_min<<' '<<y_min<<' '<<x_max<<' '<<y_max<<'\n';
	}
	return 0;
}