HDU 2028 Lowest Common Multiple Plus，求一串数字的最小公倍数

最小公倍数"/>

HDU 2028 Lowest Common Multiple Plus，求一串数字的最小公倍数

咸鱼的我，过会去抓白秋炼。

首先是参考大佬的AC代码，加上自己的修改（输入中含有0的处理）

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
int GCD(int a,int b){return b==0?a:GCD(b,a%b);
}
int main(){int n;int max1,x,i;while(~scanf("%d",&n)){max1=1;for(i=0;i<n;i++){cin>>x;if(x==0){max1=0;while(i<n){cin>>x;i++;}break;}max1=x/GCD(x,max1)*max1;}cout<<max1<<endl;}return 0;
}

这是我的

下面是大佬的

#include <iostream>
using namespace std;
int GCD(int x,int y)
{return y==0?x:GCD(y,x%y);
}
int main()
{int n,x;while(cin>>n){int ans=1;for(int i=0;i<n;i++){cin>>x;ans=x/GCD(ans,x)*ans;}cout<<ans<<endl;}return 0;
}

方法：就是，迭代到顶层，大佬的写法令人耳目一新。

思路：最小公倍数（X,Y） * 最大公约数（X,Y）=X*Y

先除后乘可以避免超界，或者用long int;

附带一份错误代码（无法解决 输入数据 5 ，2 3 4 6 9）

正确答案 36  错误代码的输出是 1296（即36^2，即2*3*4*6*9）,原因是没有用乘积一边乘一边除以因数

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
long int zd(int a,int b){int i=0;while(a%b!=0){i=a%b;a=b;b=i;}return b;
}int main(){int n;int a,b;int c[100]={0};long long int max1;while(~scanf("%d",&n)){max1=1;for(int i=0;i<n;i++){cin>>c[i];if(c[i] == 0){max1=0;break;}max1*=c[i];}if(max1==0){cout<<0<<endl;break;}a=c[0];for(int i=1;i<n;i++){b=c[i];a=zd(a,b);max1/=a;}cout<<max1<<endl;}return 0;