杭电oj 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

两个数的最大公约数和最小公倍数的乘积等于原来两个数的乘积。

这里是求N个数的最小公倍数，我们只需要两个两个求，用前两个的结果和后一个再进行求值。这样数组中的最后一项就是N个数的最下公倍数了。

#include <stdio.h>

#include <stdlib.h>

int main()

{

    int gcd(int a,int b);

    int a[100];

    int i,n;

    while(scanf("%d",&n)!=EOF)

    {

        for(i=0;i<n;i++)

        {

            scanf("%d",&a[i]);

            if(i!=0)

            {

                a[i] = a[i-1]/gcd(a[i-1],a[i])*a[i];//由“最大公约数和最小公倍数的乘积是原来两个数的乘积”转换而来

            }

        }

        printf("%d\n",a[n-1]);

    }

    return 0;

}

int gcd(int a,int b)//辗转相除法求最大公约数

{

    int c;

    while(b)

    {

        c = a;

        a = b;

        b = c%b;

    }

    return a;

}

巴特西

杭电oj Lowest Common Multiple Plus

最新文章

热门文章