[백준] 9613번 : GCD합 Silver4(실버4) - JAVA[자바]

[Silver IV] GCD 합 - 9613

문제 링크

성능 요약

메모리: 11552 KB, 시간: 76 ms

분류

유클리드 호제법, 수학, 정수론

제출 일자

2023년 11월 26일 10:53:59

문제 설명

양의 정수 n개가 주어졌을 때, 가능한 모든 쌍의 GCD의 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n (1 < n ≤ 100)가 주어지고, 다음에는 n개의 수가 주어진다. 입력으로 주어지는 수는 1,000,000을 넘지 않는다.

출력

각 테스트 케이스마다 가능한 모든 쌍의 GCD의 합을 출력한다.

 

 

1. 2중 for문으로 일어날 수 있는 상황을 다 처리해줌

2. 한 원소의 값은 최대 100만으로 100개의 원소 중 2개를 뽑는 경우의 수는 int의 범위를 넘어서니까 Long으로 처리해주어야 함

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int t = Integer.parseInt(br.readLine());
        for(int tc = 0; tc < t; tc++){
            st = new StringTokenizer(br.readLine());
            int[] arr = new int[Integer.parseInt(st.nextToken())];
            for(int i = 0; i < arr.length; i++){
                arr[i] = Integer.parseInt(st.nextToken());
            }
            long result = 0;
            for(int i = 0; i < arr.length-1; i++){
                for(int j = i + 1; j < arr.length; j++){
                    result += GCD(arr[i], arr[j]);
                }
            }
            System.out.println(result);
        }

    }

    private static int GCD(int a, int b) {
        while(b != 0){
            int tmp = a % b;
            a = b;
            b = tmp;
        }
        return a;
    }
}