SDUT 1224/HDU 1019 Least Common Multiple Ⅰ
2047 ワード
Least Common Multiple Ⅰ
Time Limit:1000 ms Memory limit:65536 K質問は?ここをクリック^^;テーマの説明はn個の数の最小の公倍数を求めます.入力入力には複数のテストインスタンスが含まれ、各テストインスタンスの開始は正の整数nであり、次いでnの正の整数である.出力は、各テストデータのセットの最小公倍数として出力され、各テストインスタンスの出力は1行を占めます.最後の出力は32ビットの整数だと仮定できます.サンプル入力
2 4 6 3 2 5 7
サンプル出力
12 70
2つの数の最大共倍数=(2つの数の積)/(最大公約数);
コード:
#include <bits/stdc++.h>
using namespace std;
int GCD(int a,int b)
{
if(a < b) {int t = a; a = b; b = t;}
if(a % b == 0) return b;
else return GCD(b,a%b);
}
int LCM(int a,int b)
{
return a / GCD(a,b) * b;
}
int main()
{
std::ios::sync_with_stdio(false);
int n,a;
while(cin>>n)
{
int last = 1;
for(int i=0;i<n;i++)
{
cin>>a;
last = LCM(a,last);
}
cout<<last<<endl;
}
return 0;
}