codeup 5.2 Least Common Multiple

問題 A: Least Common Multiple

時間限制: 1 Sec  記憶體限制: 32 MB

送出: 442  解決: 208

[​​​送出​​​][​​狀态​​​][​​讨論版​​][命題人:外部導入]

題目描述

The least common multiple (LCM) of a set of positive integers is the smallest positive integer which is divisible by all the numbers in the set. For example, the LCM of 5, 7 and 15 is 105.

輸入

Input will consist of multiple problem instances. The first line of the input will contain a single integer indicating the number of problem instances. Each instance will consist of a single line of the form m n1 n2 n3 ... nm where m is the number of integers in the set and n1 ... nm are the integers. All integers will be positive and lie within the range of a 32-bit integer.

輸出

樣例輸入

2
2 3 5
3 4 6 12      

樣例輸出

15
12      

#include<iostream>     
#include<algorithm>
using namespace std;

const int N=1e6;
int a[N];
int T,n;

bool isAllDiv(int x){
  for(int i=0;i<n;i++){
    if(x%a[i]!=0) return false; 
  }
  return true;
}

int main(){
  
  cin>>T;
  while(T--){
    cin>>n;
    for(int i=0;i<n;i++){
      cin>>a[i];
    }
    int max=*max_element(a,a+n);
    for(int i=1;;i++){
      if(isAllDiv(max*i)){
        cout<<max*i<<endl;
        break;
      }
    }
  }
  return 0;
}