HDU2028 Lowest Common Multiple Plus

秒速五厘米 2022-05-11 09:24 162阅读 0赞

Time Limit: 2000/1000 MS (Java/Others)
    
    Memory Limit: 65536/32768 K (Java/Others)
    [显示标签]
    Description
    求n个数的最小公倍数。
    Input
    输入包含多个测试实例，每个测试实例的开始是一个正整数n，然后是n个正整数。
    Output
    为每组测试数据输出它们的最小公倍数，每个测试实例的输出占一行。你可以假设最后的输出是一个32位的整数。
    Sample Input
    
    2 4 6
    3 2 5 7
    
    Sample Output
    
    12
    70
    
    Hint
    lcy
    Source
       C语言程序设计练习（五）  
    Related problem
    2024 2031 2032 2023 2034

最小公倍数可以暴力求解，如有两数a,b;做个循环，从较小的数（int min=a<b?a:b）开始，到a\*b之间必有其最小公倍数，但是这样做很耗时间，在ACM上会报错OLE;还有其他算法，更合理：

两个数的最小公倍数=两数积/最大公因数；

最大公因数可通过辗转相除法来计算，这是种比较常见的、快速的计算方式。

在下先写两个函数，分别求两数的最大公约数以及最小公倍数；再到主函数中调用。很方便。

代码如下：

#include <iostream>
    using namespace std;
    int GCD(int a,int b)
    {
        if(a<b)
        {
         int temp=a;
            a=b;
            b=temp;
        }
        if(a%b==0)
            return b;
        else
            return GCD(b,a%b)
    }
    int LCM(int a,int b)
    {
        return a*b/GCD(a,b);
    }
    int main ()
    {
    int m,n,i;
    while(cin>>n)
    {
        int s=1;
        for(i=0;i<n;i++)
        {
            cin>>m;
            s=LCM(s,m);
        }
        cout<<s<<endl;
    }
    ]