杭电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
",a[n-1]);
    }
    return 0;
}

int gcd(int a,int b)//辗转相除法求最大公约数
{
    int c;
    while(b)
    {
        c = a;
        a = b;
        b = c%b;
    }
    return a;
}