BOJ 9613. GCD 합

BOJ 9613. GCD 합

풀이

첫 줄에는 테스트 케이스 개수 t(1<=t<100)이 주어지고  그다음 줄부터 테스트 케이스를 입력받는다.
첫 줄에 테스트를 할 수의 개수 n (1<n<=100)이 주어지고, 그다음 n개의 수가 주어진다.

4 10 20 30 40

10과 20의 최대공약수, 20과 30의 최대공약수, 30과 40의 최대공약수를 각각 구하여 모두 더한다.

import java.util.Scanner;

class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();

        while (t-- > 0) {
            int tc = sc.nextInt();
            int[] arr = new int[tc];
            long sum = 0;

            for (int i = 0; i < tc; i++) {
                arr[i] = sc.nextInt();
            }

            for (int i = 0; i < tc; i++) {
                for (int j = i + 1; j < tc; j++) {
                    sum += getGCD(arr[i], arr[j]);
                }
            }
            System.out.println(sum);
        }
        sc.close();
    }

    static int getGCD(int a, int b) {
        while (b != 0) {
            int r = a % b;
            a = b;
            b = r;
        }
        return a;
    }
}

fun main() {
    repeat(readLine()!!.toInt()) {
        val arr = readLine()!!.split(" ").map { it.toLong() }
        val sum = (1 until arr.size).map { i ->
            (1 until i).map { j ->
                getGCD(arr[i], arr[j])
            }.sum()
        }.sum()
        println(sum)
    }

}

fun getGCD(a: Long, b: Long): Long = if (b == 0L) a else getGCD(b, a % b)

풀이소스

github.com/beomjo/algorithm-study/blob/main/BOJ/java/9613.java github.com/beomjo/algorithm-study/blob/main/BOJ/kotlin/9613.kt