南京教育网站开发/培训方案

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2028
Problem Description
求n个数的最小公倍数。

Input
输入包含多个测试实例，每个测试实例的开始是一个正整数n，然后是n个正整数。

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

Sample Input
2 4 6
3 2 5 7

Sample Output
12
70

GCD求最大公约数，两个数相乘之后除以最大公约数就是最小公倍数
AC代码：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<sstream>
using namespace std;
typedef long long ll;
int gcd(int a,int b) {return b==0?a:gcd(b,a%b);
}
int cmp(int a,int b){return a>b;
}
int main() {int n;while(scanf("%d",&n)==1) {int *a=new int[n];for(int i=0; i<n; i++) {scanf("%d",&a[i]);}sort(a,a+n,cmp);int ans=a[0]/gcd(a[0],a[1])*a[1];for(int i=2; i<n; i++) {if(ans>a[i]) {ans=ans/gcd(ans,a[i])*a[i];} else {ans=ans/gcd(a[i],ans)*a[i];}}printf("%d\n",ans);delete a;}return 0;}