UVa : 11827 - Maximum GCD
問題概要
http://uva.onlinejudge.org/external/118/11827.html
N個の整数が与えられる.
これらの中から2個の数を選択しGCDを取るとき, GCDの値の最大値を答えよ.
アルゴリズム
素直に実装しました.
2個の数字をどれにするか二重ループで選択して, GCDの計算結果で最大値を更新します.
プログラム
Scanner sc = new Scanner(System.in); int T = Integer.parseInt(sc.nextLine()); while(T-- > 0){ String[] s = sc.nextLine().split(" +"); int n = s.length; BigInteger ans = BigInteger.ZERO; for(int i=0;i<n;i++){ for(int j=i+1;j<n;j++){ BigInteger gcd = new BigInteger(s[i]).gcd(new BigInteger(s[j])); if(ans.compareTo(gcd) < 0){ ans = gcd; } } } System.out.println(ans); }