首页 > 代码库 > GDUFE ACM-1003

GDUFE ACM-1003

2024-08-20 17:37:50   220人阅读

Lowest Common Multiple Plus

Time Limit: 2000/1000ms (Java/Others)

Problem Description:

求n个数的最小公倍数。

Input:

输入包含多个测试实例，每个测试实例的开始是一个正整数n（2<=n<=100)，然后是n个正整数(数字均大于0）。

Output:

为每组测试数据输出它们的最小公倍数，每个测试实例的输出占一行。你可以假设最后的输出是一个64位的整数。

Sample Input:

2 3 4 
3 23 45 2

Sample Output:

12
2070
超时代码：
 1 #include<stdio.h>
 2 int main()
 3 {
 4     long long int n,a,i,k,t,min,j,s[200];
 5     while(scanf("%lld",&n)!=EOF)
 6     {
 7         for(i=0;i<n;i++)
 8         {
 9         scanf("%lld",&s[i]);
10         long long int min=s[0];
11         }
12         a=1,k=0;
13         for(i=0;i<n;i++)
14         {
15             a=a*s[i];
16             if(min>s[i])
17             min=s[i];
18         }
19         for(i=min;i>=1;--i)
20         {
21         for(j=0;j<n;++j)
22             if(s[j]%i==0)
23                 ++k;
24         if(k==n)
25         {
26             t=i;
27             break;
28         }
29         else
30             k=0;
31         }
32         printf("%lld\n",a/t);
33     }
34     return 0;
35 }

超时好烦。。。。。。。最后换了一种思路。。。。。。。/*<>*/

AC代码：

 1 #include<stdio.h>
 2 long long int s(long long int a,long long int b)
 3 {
 4     long long int f,t;
 5     long long int p=a,k=b;
 6     if(a<b)
 7     {
 8         t=a;
 9         a=b;
10         b=t;
11     }
12     while(b!=0)
13     {
14         f=a%b;
15         a=b;
16         b=f;
17     }
18     return p/a*k;
19 }
20 int main()
21 {
22     long long int n,m,a[100],i;
23     while(scanf("%lld",&n)!=EOF)
24     {
25         if(n==0)
26         continue;
27         m=1;
28         for(i=0;i<n;i++)
29         {
30             scanf("%lld",&a[i]);
31             m=s(a[i],m);
32         }
33         printf("%lld\n",m);
34     }
35     return 0;
36 }

应该还有更好的做法。。。。。。望大佬指点。。。。。。

GDUFE ACM-1003


联系
我们