(C++) - 백준(BOJ) 9613번 : GCD합

배열 안에 있는 요소들 중 한 쌍이 나오는 모든 조합들의 GCD를 구해서 다 합친게 답입니다. GCD는 유클리드 호제법으로 뚝딱 구할 수 있습니다.

뚝~딱!

#include <iostream>
#include <cstring>
using namespace std;
int GCD(int a, int b)
{
    if (!b) return a;
    GCD(b, a%b);
}
int main() {
    
    int t;
    long long a[101];
    cin >> t;
    while (t--)
    {
        int n;
        long long sum = 0;
        memset(a, 0, sizeof(a));
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        for (int i = 1; i <= n-1; i++)
            for (int j = i + 1; j <= n; j++)
                sum += GCD(a[i], a[j]);
        cout << sum << '\n';
    }
}