最大公约数

Summary

欧几里得算法即辗转相除法，用 gcd(a,b)=gcd(b,a mod b) 递推求两个整数的最大公约数，给出递归与迭代两种写法。扩展欧几里得算法在求最大公约数的同时，解出方程 ax+by=gcd(a,b) 的一组整数系数，通过递归回代由子问题的解推出当前解，同样给出返回三元组与借助引用参数两种实现。二者是求逆元、解线性同余方程与二元一次不定方程的基础工具。

参考资料

• 最大公约数 - OI Wiki

欧几里得算法

欧几里得算法（辗转相除法）可以求两个整数的 最大公约数（Greatest Common Divisor，GCD）。

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

递归

46 Bcpp

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

迭代

74 Bcpp

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

扩展欧几里得算法

扩展欧几里得算法（Extended Euclidean Algorithm，EXGCD）可以求 $ax+by=\gcd(a,b)$ 的一组整数解。

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

元组

110 Bcpp

tuple<ll,ll,ll> exgcd(ll a,ll b)
{
	if(!b)return {a,1,0};
	auto [g,x,y]=exgcd(b,a%b);
	return {g,y,x-a/b*y};
}

引用

110 Bcpp

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

例题

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

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

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

洛谷 P1082 [NOIP 2012 提高组] 同余方程

求同余方程 $ax\equiv1\pmod b$ 的最小正整数解。（$a,b\le2\times10^9$）