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