HDU2028 Lowest Common Multiple Plus【stein算法】【水题】

本文主要是介绍HDU2028 Lowest Common Multiple Plus【stein算法】【水题】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Problem Description
求n个数的最小公倍数。
 
Input
输入包含多个测试实例，每个测试实例的开始是一个正整数n，然后是n个正整数。
 
Output
为每组测试数据输出它们的最小公倍数，每个测试实例的输出占一行。你可以假设最后的输出是一个32位的整数。
 
Sample Input
2 4 6
3 2 5 7
 
Sample Output
12
70
 
Author

lcy

思路：没有用欧几里得算法来求，用的是stein算法试一下。最大公约数、

最小公倍数的欧几里得算法和stein算法参考博文：

http://blog.csdn.net/lianai911/article/details/42003903

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;int GCD(int a,int b)
{if(a == 0)return b;if(b == 0)return a;if(~a & 1){if(b & 1)return GCD(a>>1, b);elsereturn GCD(a>>1, b>>1)<<1;}if(~b & 1)return GCD(a, b>>1);if(a > b)return GCD((a-b)>>1, b);return GCD((b-a)>>1,a);
}int LCM(int a,int b)
{return a/GCD(a,b)*b;
}
int main()
{int N,d;while(cin >> N){int ans = 1;for(int i = 1; i <= N; ++i){cin >> d;ans = LCM(ans,d);}cout << ans << endl;}return 0;
}

这篇关于HDU2028 Lowest Common Multiple Plus【stein算法】【水题】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---