Lowest Common Multiple Plus

此博客链接：https://www.cnblogs.com/ping2yingshi/p/12368569.html

Lowest Common Multiple Plus（73min)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2028

Problem Description

求n个数的最小公倍数。

Input

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

Output

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

Sample Input

2 4 6

3 2 5 7

Sample Output

题解：

方法：两数求最小公倍数，用辗转相除求最大公约数，最小公倍数等于两数乘积除以最大公约数。

思路：多数求最小公倍数：

1.先用转转相除法求前两个数的最大公约数a，最小公倍数b=前两个数乘积/最大公约数a，

2.再用b和下一个数求得最小公倍数，

.......以此类推。

辗转相除法说明：用两个数中的较大的数a除以较小的数b，得到余数c,再用余数c除以除数b得到新的余数，再用除数b除以新的余数，直到余数为零时，除数则是最大公约数。

注意！注意！注意！在求最小公倍数时要先除以最大公约数再乘以另外一个数，要不然两个数的乘积可能会超出整型范围。

代码如下：

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<string.h>
int main()
{
    int n;
    int n1;
    int n2;
    while (~scanf_s("%d",&n))
    {
        int arr[1000];
        int j = 0;
        int temp = 0;
        for (int i=0;i<n;i++)//读取数据
        {
            scanf_s("%d", &arr[i]);
        }
        for ( j = 0; j < n - 1; j++)
        {
            n1 = arr[j];
            n2 = arr[j + 1];
            while (n1 % n2 != 0)//辗转相除法求最大公约数
            {
                temp = n1 % n2;
                n1 = n2;
                n2 = temp;
            }
            arr[j + 1] = arr[j + 1] / n2 * arr[j];//求最小公倍数
        }
        printf("%d
", arr[j]);
       
    }
    return 0;
}

Lowest Common Multiple Plus

相关推荐