[백준 9613] GCD 합, C++

https://www.acmicpc.net/problem/9613

9613번: GCD 합

 본 문제는 2013 ACM-ICPC Asia Phuket Regional Programming Contest PE번 문제로 양의 정수 n개가 주어졌을 때, 가능한 모든 쌍의 GCD의 합을 구하는 문제다. 여기서 GCD는 최대공약수를 뜻한다. GCD는 유클리드 호제법으로 코딩할 수 있다. 따라서, 유클리드 호제법을 이용한 GCD의 모든 경우의 수를 더하여 출력하면 되는 문제다.

1. 배열에서 모든 GCD의 결과를 구한다.
2. GCD의 결과의 합을 구한다.

#include <cstdio>
 
using namespace std;
 
// 유클리드 호제법
int cal(int x, int y) {
    if (y == 0) return x;
    else return cal(y, x%y);
}
 
int main() {
    int a[101];
    int t;
    scanf("%d", &t);
    while (t--) {
        int n;
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            scanf("%d", &a[i]);
        }
        long long ans = 0LL;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (i == j) continue;
                ans += cal(a[i], a[j]);
            }
        }
        printf("%lld\n", ans);
    }
}