3002 Jackpot
問題概要
n個の数字の最大公約数を求める。
それが10億より大きくなるならMore than a billionを出力。
解法
LCM(a,b)=a*b/GCD(a,b)
数が3つ以上になっても同様。
g++の場合GCDはalgorithm内に__gcdがあるためそれを使うと楽。
ソースコード
int main() { int T; cin>>T; rep(U,T){ int n; cin>>n; ll a=1,t; rep(i,n){ cin>>t; if(!a)continue; a*=t/__gcd(a,t); if(a>1000000000)a=-1; } if(!a)cout<<"More than a billion."<<endl; else cout<<a<<endl; } return 0; }