最大公约数、最小公倍数

1. 辗转相除法求最大公约数

辗转相除法是用于求两个非负整数 a 、 b 的最大公约数(gcd、Greatest Common Divisor)的方法，其基本逻辑如下：
直到时，就可得：

注意：

C语言实现：

// a must geq than b.
int gcd(int a, int b)
{
	int mod = a % b;
	if(mod)
		return gcd(b, mod);
	else
		return b;
}

或者：

// a must geq than b.
int gcd(int a, int b)
	return a % b ? gcd(b, a % b) : b;

用小值乘最大公约数即可。

int lcm(int a, int b)
	return a > b ? b * gcd(a, b) : a * gcd(b, a);