[백준 9613] GCD 합 [C]

백준 - 9613

---

풀이

모든 쌍의 GCD를 구해서 합해주면 된다. 단, 최악의 경우 1,000,000 * 99 * 98 * 97 *... * 3 * 2 *1 의 수가 나올 수 있으니 long long 자료형의 변수에 합을 담아주어야 한다.

 

---

소스코드

#include <stdio.h>
int GCD(int a, int b){
    return b ? GCD(b, a%b) : a;
}
int main(){
    int t, n, arr[100];
    scanf("%d", &t);
    while (t--){
        scanf("%d", &n);
        long long gcd_sum = 0;
        for (int i = 0; i < n; i++)
            scanf("%d", &arr[i]);
        for (int i = 0; i < n-1; i++)
            for (int j = 1 + i; j < n; j++)
                gcd_sum += GCD(arr[i], arr[j]);
        printf("%lld\n", gcd_sum);
    }
}

---

출처

9613번: GCD 합