hdu_1019_Least Common Multiple

hdu_1019_Least Common Multiple_201310290920

Least Common Multiple

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 24649 Accepted Submission(s): 9281

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

题意：求几个数的最小公倍数

思路:前两个数求一次，求得的结果再与下一个数求

 1 //hdu_1019_Least Common Multiple_201310290920-2
 2 #include <stdio.h>
 3 #include <malloc.h>
 4 
 5 void swap(int* a,int* b)
 6 {
 7     int t;
 8     t=*a;
 9     *a=*b;
10     *b=t;   
11 }
12 int gcd(int m,int n)
13 {
14     int i;
15     if(m>n)
16     swap(&m,&n);
17     i=m;
18     while(i)
19     {
20         i=n%m;
21         n=m;
22         m=i;
23     }
24     return n;
25 }
26 int main()
27 {
28     int N;
29     scanf("%d",&N);
30     while(N--)
31     {
32         int i,j,n,t;
33         int *shuzu;
34         scanf("%d",&n);
35         shuzu = (int*)malloc(sizeof(int)*n);
36         for(i=0;i<n;i++)
37         scanf("%d",&shuzu[i]);
38         for(i=0;i<n-1;i++)
39         {
40             t=gcd(shuzu[i],shuzu[i+1]);
41             shuzu[i+1]=shuzu[i]/t*shuzu[i+1];
42             //shuzu[i+1]=shuzu[i]*shuzu[i+1]/t;这样容易造成数据溢出 
43         }
44         printf("%d
",shuzu[n-1]);
45         free(shuzu);
46     }
47     //printf("%d
",gcd(5,15));
48     //while(1);
49     return 0;
50 }
51 //ac

 1 #include <stdio.h>
 2 #include <malloc.h>
 3 
 4 int main()
 5 {
 6     int N;
 7     scanf("%d",&N);
 8     while(N--)
 9     {
10         int i,j,n;
11         int *shuzu;
12         scanf("%d",&n);
13         shuzu = (int*)malloc(sizeof(int)*n);
14         for(i=0;i<n;i++)
15         scanf("%d",&shuzu[i]);
16         for(i=0;i<n-1;i++)
17         for(j=shuzu[i];j<=shuzu[i]*shuzu[i+1];j++)
18         if(j%shuzu[i]==0&&j%shuzu[i+1]==0)
19         {
20             shuzu[i+1]=j;
21             break;
22         }
23         printf("%d
",shuzu[n-1]);
24         free(shuzu);
25     }
26     return 0;
27 }
28 //TML