UVa 12708 : GCD The Largest
問題リンク : http://uva.onlinejudge.org/external/127/12708.pdf
問題概要 :
正の整数Nが与えられる。
N以下の任意の異なる2つの正の整数を選び、その最大公約数を求める
こうして得られる最大公約数のうち、最大のものを出力せよ
解法 :
Nが偶数のとき、N/2が最大
Nが奇数のとき、N/2の小数点以下切り捨てたものが最大
よって、N/2が答えとなる
コード :
import java.io.*; import java.util.*; class Main { public static void main(String args[]){ Scanner in = new Scanner(System.in); int T = in.nextInt(); while(T-->0){ long N = in.nextLong(); System.out.println((long)(N/2)); } } }