HDU_oj_2028 Lowest Common Multiple Plus

Problem Description

 

求n个数的最小公倍数。

 

Input

输入包含多个测试实例，每个测试实例的开始是一个正整数n，然后是n个正整数。

 

Output

为每组测试数据输出它们的最小公倍数，每个测试实例的输出占一行。你可以假设最后的输出是一个32位的整数。

 

Sample Input

2 4 6

3 2 5 7

 

Sample Output

12

70

 

分析：

以下链接有详细算法，此题选用最常用的辗转相除法

http://www.cnblogs.com/tenjl-exv/p/7993997.html

注意点：

在进行最小公倍数计算时，

两数相乘再除以最大公倍数可能会导致相乘后超出32位而错误

所以改变下运算顺序可解决

 

 

#include<iostream>
using namespace std;

//辗转相除法
//非递归 
int Gcd(int m,int n)
{
    while(n!=0)
    {
        int temp=n;
        n=m%n;
        m=temp;
    }
    return m;
}
int main()
{
    int n;
    int v,c,d;
    while(cin>>n)
    {
        cin>>v;
        while(--n)
        {
            cin>>c;
            d=Gcd(v,c);
            //v=v*d/c; 
            //若要为注释的表达式可能会导致超出32位 
            v=v/d*c;  
        }
        cout<<v<<endl;
    }
}