也称欧几里得算法

原理：

gcd(a,b)=gcd(b,a mod b)

边界条件为 gcd(a,0)=a;

其中mod 为求余

故辗转相除法可简单的表示为：

int gcd(int a, int b)

{

                 return b ==0? a:gcd( b, a% b);

}

简洁而优雅。

例如：HDU 2028 Lowest Common Multiple Plus求n个数的最小公倍数。

最小公倍数=两数之积  /  最大公约数

这里防止中间过程溢出，先除以最大公约数，然后在求积。

#include<iostream>

using namespace std;

int gcd(int a,int b)

{

	return b==0?a:gcd(b,a%b);

}

int main()

{

	int n,ans;

	while(cin>>n)

	{

		cin>>ans;

		while(--n)

		{

			int temp;

			cin>>temp;

			ans=ans/gcd(ans,temp)*temp;

		}

		cout<<ans<<endl;

	}

}