読者です 読者をやめる 読者になる 読者になる

土下座しながら探索中

主に競技プログラミング

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