1. 暴力枚举求最大公约数

   • 先找出 a 和 b 当中较小的那个

   • 从较小的数开始枚举，每次递减 1

   • 找到一个整数，同时是 a 和 b 的约数的时候跳出循环。最糟糕的情况下一直枚举到 1，因为 1 是任何整数的约数，所以这时候一定能跳出循环。

int gcd(int a,int b)
{
	if(a>b)
		swap(a,b);
	//确保a是小的那个 

	int ans;

	for(ans=a;a%ans!=0||b%ans!=0;ans--); //最糟糕的情况是ans从a枚举到1，一定会跳出循环 
	
	return ans;

}

如果 a 和 b 很大，而且 a 和 b 互质，上面的代码就很可能超时了。

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

int gcd(int a,int b)
{
	int c;
	while(a%b!=0)
	{
		c = a%b;
		a = b;
		b = c;
	}

	return b;
}

这个算法效率很高，我们需要理解和熟背。

3. 纯暴力枚举求最小公倍数

反正，就是一个个去试，而且，每次只递增 1

int gcm(int a,int b)
{
	int c=max(a,b);
	
	int ans;
	for(ans=c; ans%a!=0||ans%b!=0 ; ans++);

	return ans;
}

当 a 和 b 很大的时候，上面这个方法会超时

4. 倍增法求最小公倍数

int gcm(int a,int b)
{
	if(a<b)
		swap(a,b);
	//保证 a 是大的那个 
	
	int ans;
	for(ans=a;ans%b!=0;ans+=a);

	return ans;
}

上面代码中，ans 是从 a 开始枚举，每次递增 a ，所以它一定是 a 的倍数。所以，每次只需要校验 ans 是不是 b 的倍数即可。因为每次递增 a ，所以枚举的次数会少一些，效率也会高一些。

4. 公式法求最小公倍数

如果 a 和 b 是两个很大的质数，上面的代码仍然不够好。可以用辗转相除法先求出最大公约数，再来用公式法求最小公倍数。

存在以下公式：

a \* b = gcd(a,b) \* gcm(a,b)

所以

gcm = a * b / gcd(a,b)

5. 相关公式：

这个式子真的很重要，无论是以后大家做数学试卷还是信息学比赛，都很有用。

a \* b = gcd(a,b) \* gcm(a,b)