[유클리드 호제법] / [백준(baekjoon) 9613] GCD(최대공약수) 합

문제

백준 9613

최대공약수(GCD) 의 합을 구하시오.

원리

유클리드 호제법, GCM, LCD 설명 포스트 참고!

구현 java

1.import java.util.*;
2.
3.public class Main {
4.    public static void main(String[] args) {
5.        Scanner sc = new Scanner(System.in);
6.        int t = sc.nextInt();
7.        for (int k = 0; k < t; k++) {
8.            int n = sc.nextInt();
9.            int[] inputs = new int[n];
10.            for (int i = 0; i < n; i++) inputs[i] = sc.nextInt();
11.
12.            long sum = 0;
13.            for (int i = 0; i < n - 1; i++) {
14.                for (int j = i + 1; j < n; j++)
15.                    sum += gcd(inputs[i], inputs[j]);
16.            }
17.            System.out.println(sum);
18.        }
19.    }
20.
21.    static int gcd (int a, int b) {
22.        return b == 0 ? a : gcd(b, a % b);
23.    }
24.}

결과