求多个数的最小公倍数的问题

#include <stdio.h>
#include <stdlib.h>
typedef long unsigned lu;
lu gcd(lu a,lu b)
{
    int c;
    c=a%b;
    while(c)
    {
        a=b;
        b=c;
        c=a%b;
    }
    return b;
}
lu lcm(lu a,lu b)
{
    return a*b/gcd(a,b);
}
int main()
{
    lu t,n;
    while(scanf("%lu",&t)!=EOF)
    { lu re=1;
        while(t--)
        {
            scanf("%lu",&n);
             re=lcm(re,n);
        }
        printf("%lu\n",re);
    }
    return 0;
}

*最小公倍数与最大公约数的关系：[a1,a2,..,an]=M/(M/a1,M/a2,..,M/an)，其中M为a1,a2,..,an的乘积，a1,a2,..,an为正整数。

例如：对于4,6,8,10，有[4,6,8,10]=120，而M=4*6*8*10=1920，M/(M/a1,M/a2,..,M/an) =1920/(6*8*10,4*8*10,4*6*10,4*6*8)=1920/16=120。

*多个数最大公约数的算法实现

    求多个数最小公倍数可以转化为求多个数的最大公约数。求多个数的最大公约数(a1,a2,..,an)的传统方法是多次求两个数的最大公约数，即

（1）       用辗转相除法[2]计算a1和a2的最大公约数(a1,a2)

（2）       用辗转相除法计算(a1,a2)和a3的最大公约数，求得(a1,a2,a3)

（3）       用辗转相除法计算(a1,a2,a3)和a4的最大公约数，求得(a1,a2,a3,a4)

（4）       依此重复，直到求得(a1,a2,..,an)

上述方法需要n-1次辗转相除运算。

做此题的关键所在是找出最小公倍数与最大公约数之间的关系，即是abc的最小公倍数=a*b*c/gcd(a,b,c);所以此题又转化为求多个数的最大公约数的问题，利用辗转相除最后求得结果。