HDU1019 Least Common Multiple
HDU1019 Least Common Multiple
HDU 1019 Least Common Multiple
Time Limit: 2000/1000 MS (Java/Others) | Memory Limit: 65536/32768 K (Java/Others) |
|---|---|
Total Submission(s): 68851 | Accepted Submission(s): 26323 |
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 1Sample Output
105
10296理解：
题目的意思大致是给你k组数据，每组数据单独占一行，每行第一个数组n为该组数据的个数k，之后跟着k个数字，题目要求你求得这k个数字的最小公倍数。怎么，简单吧？但你远远想不到，提交了答案，TL等着你。
最初超时代码：
#include<iostream>
#include<vector>
using namespace std;
int gcd(int a,int b)
{
if(b==0)return a;
else
{
gcd(b,a%b);
}
}
int lcm(int a,int b)
{
return (a*b)/gcd(a,b);
}
int main()
{
vector<int>a;
int count1;
long long t,k;
long long n;
cin>>count1;
while(count1)
{
while(cin>>n)
{
for(int i=0;i<n;i++)
{
cin>>k;
a.push_back(k);
}
if(n==1)
{
cout<<k;
continue;
}
t=lcm(a[0],a[1]);
for(int i=2;i!=a.size();i++)
{
if(t%a[i]!=0||a[i]%t!=0)
t=t/gcd(t,a[i])*a[i];
}
cout<<t<<endl;
a.clear();
count1--;
}
}
}最终AC代码：
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
int gcd(int a,int b)
{
if(b==0)return a;
return gcd(b,a%b);
}
/*int lcm(int a,int b)
{
return (a*b)/gcd(a,b);
}*/
int main()
{
//vector<int>a;
int count1;
cin>>count1;
while(count1)
{
int n;
int t=1,k;
cin>>n;
/*for(int i=0;i<n;i++)
{
cin>>k;
a.push_back(k);
}*/
/*scanf("%d",&k);
t=k;
if(n==1)
{
printf("%d\n",t);
continue;
}*/
for(int i=0;i<n;i++)
{
scanf("%d",&k);
//if(a%k!=0&&k%a!=0)
t=t/gcd(t,k)*k;
}
printf("%d\n",t);
//a.clear();
count1--;
}
//return 0;
}总结超时处理方法：
- return 0；
- cin cout转为scanf printf
- 容器优化
- 循环优化
- 大数处理
- 去除没必要的函数
- 循环改写为函数
(总结：AC不易，TL比WA更难受)
腾讯云开发者
