BOJ 9613 · GCD 합

알고리즘 분류 : 수학  

최대공약수(GCD)는 유클리드 호제법을 이용하여 구할 수 있다. 자세한 내용은 이곳을 참조.

• n개의 숫자에서 가능한 모든 쌍에 대한 GCD를 구해야 하므로, 2중 for문을 통해 gcd 함수를 호출한다.
• 각 숫자 쌍에서 구한 gcd를 모두 합하여 출력한다.

---

C++ 소스코드

#include <cstdio>

int gcd(int x, int y) {
    while (y != 0) {
        int r = x%y;
        x = y;
        y = r;
    }
    return x;
}

int main() {
    int t, n, a[100];
    scanf("%d", &t);
    while (t--) {
        long long sum = 0;
        scanf("%d", &n);
        for (int i=0; i<n; i++) {
            scanf("%d", &a[i]);
        }
        for (int i=0; i<n-1; i++) {
            for (int j=i+1; j<n; j++) {
                sum += gcd(a[i], a[j]);
            }
        }
        printf("%lld\n", sum);
    }
    return 0;
}

---

Python 3 소스코드

def gcd(x, y):
    while y is not 0:
        r = x%y
        x = y
        y = r
    return x


for _ in range(int(input())):
    n, *a = map(int, input().split())
    s = 0
    for i in range(0, n-1):
        for j in range(i+1, n):
            s += gcd(a[i], a[j])
    print(s)

---

참고

• 백준 온라인 저지 : BOJ 9613