GCD 합 9613

https://www.acmicpc.net/problem/9613

유클리드 호제법을 기억해야 함

유클리드 호제법은 두 수의 최대공약수를 찾는 방법 중 하나입니다.하
이 방법은 두 수 a와 b에서 (a가 b보다 크다고 가정하겠습니다) a를
b로 나눈 나머지를 r이라 할 때, a와 b의 최대공약수는 b와 r의 최대공약수와
같다는 것을 이용합니다.

예를 들어, 두 수 48과 18의 최대공약수를 찾아보겠습니다.

    48을 18로 나눈 나머지는 12입니다. 따라서 48과 18의 최대공약수는
    18과 12의 최대공약수와 같습니다.
    18을 12로 나눈 나머지는 6입니다. 따라서 48과 18의 최대공약수는
    12와 6의 최대공약수와 같습니다.
    12를 6으로 나눈 나머지는 0입니다. 따라서 48과 18의 최대공약수는
    6과 0의 최대공약수와 같습니다.
    이제 b가 0이 되었으므로, a인 6이 48과 18의 최대공약수입니다.

이렇게 유클리드 호제법은 두 수의 나머지를 구하고, 이를 다시 나누는
과정을 반복하여 최대공약수를 찾습니다. 이 알고리즘은 재귀적으로 구현할 수
있으며, 두 수가 매우 큰 경우에도 빠르게 최대공약수를 찾을 수 있는 효율적인 방법입니다.

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int t = Integer.parseInt(br.readLine());
        String[] input;
        for (int i = 0; i < t; i++) {

            input = br.readLine().split(" ");
            int n = Integer.parseInt(input[0]);
            int[] nums = new int[n];
            for (int j = 1; j < n+1; j++) {
                nums[j-1] = Integer.parseInt(input[j]);
            }

            //최대공약수
            long answer = 0;
            for (int j = 0; j < n-1; j++) {
                for (int k = j+1; k < n; k++) {
                    int a = Math.min(nums[j], nums[k]);
                    int b = Math.max(nums[j], nums[k]);

                    int num = 1;
                    while(num != 0){
                        num = b%a;
                        if(num == 0){
                            break;
                        }
                        b = a;
                        a = num;
                    }
                    answer += a;
                }
            }

            System.out.println(answer);
        }
    }
}

시간복잡도
O(t * n^2)
이중for문 이므로 n^2 테스트 케이스 t 곱함