UC知道杭电acm1019
来源：百度知道 编辑：UC知道 时间：2024/06/15 08:26:09
题目是求最小公倍数，下面是我的代码，超时
题目网址 http://acm.hdu.edu.cn/showproblem.php?pid=1019
#include<iostream>
using namespace std;
int main()
{
int m,n,i,j;
int a[1000]={0};
while(cin>>m){
while(m){
int s=1;
cin>>n;
for(i=0;i<n;i++){
cin>>a[i];
}
for(i=0;i<n;i++){
s*=a[i];
}
for(j=a[0];j<=s;j++){
int flag=1;
for(i=0;i<n;i++){
if(j%a[i]!=0){
flag=0;
break;
}
}
if(flag){
cout<<j<<endl;
break;
}
}
m--;
}
}
return 0;
}
高手帮帮忙，最好在我的代码上改进算法
题目网址 http://acm.hdu.edu.cn/showproblem.php?pid=1019
#include<iostream>
using namespace std;
int main()
{
int m,n,i,j;
int a[1000]={0};
while(cin>>m){
while(m){
int s=1;
cin>>n;
for(i=0;i<n;i++){
cin>>a[i];
}
for(i=0;i<n;i++){
s*=a[i];
}
for(j=a[0];j<=s;j++){
int flag=1;
for(i=0;i<n;i++){
if(j%a[i]!=0){
flag=0;
break;
}
}
if(flag){
cout<<j<<endl;
break;
}
}
m--;
}
}
return 0;
}
高手帮帮忙，最好在我的代码上改进算法
您好
这道题不能使用您的算法来做
首先：复杂度过高，造成超时
其次：
for(i=0;i<n;i++){
s*=a[i];
}
s的值一定会溢出的，题中每一个数都可能是一个32位的整数，乘起来数量级可想而知，就算不超时也算不对的。
您可以试试这样的数据：
1
10
12345
23456
34567
45678
567890
23
27
2191
7777777
8888888
333
您不妨试试这样的算法思路：
#include <cstdio>
long gcb( long a, long b)
{
long r;
if(a<b)
{
r=a;
a=b;
b=r;
}
while(b)
{
r=a%b;
a=b;
b=r;
}
return a;
}
int main()
{
long a[1000];
int n;
scanf("%d",&n);
while(n--)
{
int num;
scanf("%d",&num);
int i;
for( i=1;i<=num;i++)
scanf("%ld",&a[i]);
long temp=1;
for(i=1;i+1<=num;i++)
{
temp=a[i]/gcb(a[i+1],a[i])*a[i+1];
a[i+1]=temp;