HDOJ 1019 Least Common Multiple ―― N个数的最小公倍数求法【题解经验】

Least Common Multiple
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 4624    Accepted Submission(s): 1665

Problem Description
The least common multiple (LCM) of a set of positive integers is the smallest positive integer which is divisible by all the numbers in the set. For example, the LCM of 5, 7 and 15 is 105.

 

Input
Input will consist of multiple problem instances. The first line of the input will contain a single integer indicating the number of problem instances. Each instance will consist of a single line of the form m n1 n2 n3 ... nm where m is the number of integers in the set and n1 ... nm are the integers. All integers will be positive and lie within the range of a 32-bit integer.

 

Output
For each problem instance, output a single line containing the corresponding LCM. All results will lie in the range of a 32-bit integer.

 

Sample Input
2
3 5 7 15
6 4 10296 936 1287 792 1
 

Sample Output
105
10296
 

Source
East Central North America 2003, Practice
 

Recommend
JGShining

#include <iostream>

#define N 10000

long getgcd(__int64 a,__int64 b)//传说中的辗转相除法
{
    __int64 gcd,num1,num2;
    num1=(a>b)?a:b;
    num2=(a<b)?a:b;
    gcd=num2;
    num1=num1%num2;
    while(1)
    {
        num1=num1%num2;
        if(num1==0)
        {
            gcd=num2;
            break;
        }
        num2=num2%num1;
        if(num2==0)
        {
            gcd=num1;
            break;
        }
    }
    return gcd;
}

int main()
{
    __int64 thenum,lcm;
    int n,num;
    int i,j,k;
   
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&num);
       
        lcm=1;
        for(j=1;j<=num;j++)
        {
            scanf("%I64ld",&thenum);
            lcm=lcm*thenum/getgcd(lcm,thenum);
        }
       
        printf< font color="#ff00ff">("%I64ld\n",lcm);
    }
   
    return 0;
}

心得：