[JAVA] 백준 수학 연습문제 - BOJ 9613

여러개의 수들의 GCD 총 합 구하기, 오답처리 시 int범위 초과 고려해야함.

 

유클리드 호제법으로 GCD를 쉽게 구할 수 있으나,

최대 입력 100개가 모두 최대 정수 1,000,000일 경우의 GCD는 49.5억으로 int범위를 벗어난다.

 

자바는 int의 최대 양수 범위에서 벗어난 만큼 int의 최소 음수에 더해지므로, 런타임에러가 아닌 오답처리가 된다.

 

즉, 오답처리가 되었다면 데이터 타입의 범위가 넘어간 경우일 수 있으니 참고한다.

 

import java.util.Scanner;
public class BOJ9613 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t=sc.nextInt();

        while(t-->0){
            long gcd=0;
            int n=sc.nextInt();
            int[] nums=new int[n];

            for(int i=0;i<n;i++){
                nums[i]=sc.nextInt();
                for(int j=i-1;j>=0;j--){
                    gcd+=GCD(nums[i],nums[j]);
                }
            }
            System.out.println(gcd);
        }
    }
    static int GCD(int a,int b){
        while(b!=0){
            int r=a%b;
            a=b;
            b=r;
        }
        return a;
    }
}