HDU2028（解题报告）

2024-09-07 20:32

文章标签 报告解题 hdu2028

本文主要是介绍HDU2028（解题报告），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Lowest Common Multiple Plus

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 30563 Accepted Submission(s): 12386

Problem Description

求n个数的最小公倍数。

Input

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

Output

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

Sample Input

  2 4 6
3 2 5 7

Sample Output

  12
70

Author

lcy

解题思想：
   刚看到这道题，完全是当水题做得，当提交报wrong后，才发现在计算最小公倍数是，如果用(n*m) / (gdc(n,m))，可能会造成数组溢出，
换一种方法，改成n / ( gdc(n,m) ) * m可以有效避免溢出。
   剩下的就是常规方法水，n个数的最小公倍数。先求出开始两个的最小公倍数，然后和第二个数在进行求解，求出最小最公倍数。总之
就是前面的最小公倍数和后面的数做计算，最后求出的最小公倍数就是n个数的最小公倍数。

解题代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int a[10000];

int gdc(int a,int b)
{
    return a==0?b:gdc(b%a,a);
}

int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        int k,l=1;
        int t;
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
        }
        sort(a,a+n);
        k=gdc(a[0],a[1]);
        l=a[0]*a[1];
        t=l/k;
        for(int i=2;i<n;i++)
        {
            k=gdc(t,a[i]);
            /*l=t*a[i];
            t=l/k;*/
            t=t/k*a[i];
        }
        printf("%d\n",t);
    }
}

这篇关于HDU2028（解题报告）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！