数论相关

辗转相除法

用于求两个数的最大公约数

int GCD(int a, int b)
{
	return (b == 0) ? a : GCD(b, a % b);
}

扩展欧几里得算法

用于求ax + by = GCD(a, b)

int exGCD(int a, int b, int & x, int & y)
{
	int d = a;
	if(b != 0)
	{
		d = exGCD(b, a % b, y, x);
		y -= (a / b) * x;
	}
	else
	{
		x = 1;
		y = 0;
	}
	return d;
}