杭电ACM-2028

题目：

2028题

错误代码：

错误代码！！！
#include<stdio.h>
int gcd(int x,int y)//求2个数的最大公约数
{
    if(y==0) return x;//x即为最大公约数
    else return gcd(y,x%y);
}
int main()
{
    int a,b,n,i;//n为总的数字个数，a为第一个数，b为后面输入的数字
    long long sum;
    while(~scanf("%d",&n))
    {
        scanf("%d",&a);//先将第一个数输入进去
        sum=a;
        for(i=1;i<n;i++)
        {
            scanf("%d",&b);
            a=gcd(a,b);//找出a，b中的最大公约数
            sum=sum/a*b;//sum为a，b的最小公倍数 先除法再乘法是为了防止溢出
        }
        printf("%lld\n",sum);
    }
    return 0;
}

所以为什么错误呢？？？

错误原因：sum为前面数的最小公倍数，第二次求最大公约数的时候不应该用前面的最大公约数和后面的数求最大公约数，而是应该用前面的最小公倍数与后面的数求最大公约数（很绕吧 ๑•ᴗ•๑）

正确代码：

#include<stdio.h>
int gcd(int x,int y)//求2个数的最大公约数
{
    if(y==0) return x;//x即为最大公约数
    else return gcd(y,x%y);
}
int main()
{
    int a,b,n,i;//n为总的数字个数，a为第一个数，b为后面输入的数字
    while(~scanf("%d",&n))
    {
        scanf("%d",&a);//先将第一个数输入进去
        for(i=1;i<n;i++)
        {
            scanf("%d",&b);
            a=a/gcd(a,b)*b;
        }
        printf("%d\n",a);
    }
    return 0;
}

总结：对于一串数字求取最小公倍数的算法就是将前面2个数求取最小公倍数，再用这个最小公倍数与第三个数找它俩的最小公倍数，再用这个最小公倍数与第四个数找它俩的最小公倍数……
（两个数的最小公倍数就可以代表这2个数！！！相当于2个数合成为1个数）