hdu 2028 Lowest Common Multiple Plus

http://acm.hdu.edu.cn/showproblem.php?pid=2028

题目大意

求n个数的最小公倍数。输入包含多个测试实例,每个测试实例的开始是一个正整数n,然后是n个正整数。

Sample Input

2 4 6

3 2 5 7

Sample Output

12

70

方法与总结

  • 先求前两个数的最小公倍数x,再求x与第三个数的最小公倍数,以此类推
  • 注意在用最大公约数求最小公倍数的时候不能用a*b/gcd(a,b),因为这样会越界,提交的时候会出现WA,应改为a/gcd*b

代码

#include<iostream>
using namespace std;

int Gcd(int a, int b)
{
    if(b!=0)
        return Gcd(b, a%b);
    return a;
}

int Lcm(int a,int b)
{
    return a/Gcd(a,b)*b;
}

int main()
{
    int n;
    while(cin>>n)
    {
        int *a=new int[n];
        for(int i=0;i<n;i++)
            cin>>a[i];
        long x=a[0];
        for(int i=1;i<n;i++)
            x=Lcm(x,a[i]);
        cout<<x<<endl;
    }
    return 0;
}
/* bottom:40px 距浏览器底部距离 right:40px 距浏览器右边距离 */