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;
}