最大公约数(GCD)

欧几里德算法

GCD，也叫辗转相除法。

#include <iostream>
using namespace std;

int gcd(int ai, int bi)
{
	return bi ? gcd(bi, ai % bi) : ai;
}

int main()
{
	int n;
	cin >> n;
	while (n--)
	{
		int ai, bi;
		scanf("%d%d", &ai, &bi);
		printf("%d\n", gcd(ai, bi));
	}
	return 0;
}

扩展欧几里德算法

扩展欧几里德算法可以用于求解逆元，利用的原理就是 $a \times x + b \times y = 1 $。

如求 ${a \over b} \equiv {a \times x (mod \, p)}$ 的逆元:

有 $b \times x \equiv 1 \, (mod \, p)$

即 $b \times x - \lfloor {b \times x \over p} \rfloor \times p = 1$

此时就可使用扩展欧几里德算法求解，公式为 $gcd(b,p,x,y)$其中求出的 $x$ 就是逆元。

#include <iostream>
using namespace std;

int exgcd(int ai, int bi, int &xi, int &yi)
{
	if (!bi)
	{
		xi = 1, yi = 0;
		return ai;
	}
	int res = exgcd(bi, ai % bi, yi, xi);
	yi -= ai / bi * xi;
	return res;
}
//如何理解这里的递归和yi的更新

int main()
{
	int n;
	cin >> n;
	while (n--)
	{
		int ai, bi, xi, yi;
		scanf("%d%d", &ai, &bi);
		exgcd(ai, bi, xi, yi);
		printf("%d %d\n", xi, yi);
	}
	return 0;
}