HDOJ 1019 Least Common Multiple （数论）

交了4次才过，

以为很简单，结果大意了。。

注意两个问题：

一个是考虑可能的溢出情况，这个以前就遇到过，所以这里没有忘记

 1 int lcm(int a, int b)
 2 {
 3     return a/gcd(a,b)*b;
 4 }
 5 
 6 
 7 //避免写成这样
 8 int lcm(int a, int b)
 9 {
10     return a*b/gcd(a,b); //可能会溢出
11 }

第二个是
考虑特殊数据

1 //如果数据是这个样子的
2 2
3 1 3
4 1 4
5 
6 这样只有一个数据
7 那么直接输入a[0]，即为最大公约数了

考虑以上就能轻松AC

 1 #include<iostream>
 2 
 3 using namespace std;
 4 
 5 int gcd(int a, int b)
 6 {
 7     if(a<b) 
 8     {
 9         int t =a;
10         a = b;
11         b = t;
12     }
13     return b==0?a:gcd(b,a%b);
14 }
15 int lcm(int a, int b)
16 {
17     return a/gcd(a,b)*b;
18 }
19 
20 int main()
21 {
22 
23     int i,j,n,m;
24     int a[1000] = {0};
25     int ans = 0;
26     scanf("%d",&m);
27     for(i=0;i<m;i++)
28     {
29         scanf("%d",&n);
30         scanf("%d",&a[0]);
31         if(n == 1)
32             printf("%d
",a[0]);
33         else
34         {
35             for(j=1;j<n;j++)
36             {
37                 scanf("%d",&a[j]);
38                 ans = lcm(a[j],a[j-1]);
39                 a[j] = ans;
40             }
41             printf("%d
",ans);
42         }
43     }    
44     return 0;
45 }