백준 9613번 GCD 합 JAVA

링크텍스트

설명

최대 100C2 = 100! / (2! × 98!), 4950번 연산한다. 최대 공약수가 모두 100만인 경우 int의 범위를 넘기때문에 long으로 선언하지 않으면 오버플로우 난다.
시간복잡도: O(T*N²), 공간복잡도: O(N)

회독

• [ x ] 1회
• 2회
• 3회

코드

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

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int t = Integer.parseInt(br.readLine());

        while(t-->0){
            StringTokenizer st = new StringTokenizer(br.readLine());

            int n = Integer.parseInt(st.nextToken());

            int [] arr = new int[n];
            for(int i=0;i<n;i++){
                arr[i] = Integer.parseInt(st.nextToken());
            }

            long sum = 0;
            for(int i=0;i<n-1;i++){
                for(int j=i+1;j<n;j++){
                    int a = arr[i];
                    int b = arr[j];
                    sum+=GCD(a,b);
                }
            }

            sb.append(sum).append("\n");
        }

        System.out.print(sb);
    }

    public static int GCD(int a, int b){
        while(b>0){
            int temp = a%b;
            a = b;
            b = temp;
        }return a;
    }
}