9613번: GCD 합

GCD는 최대 공약수를 의미한다.

유클리드 호제법을 이용해 간단하게 문제를 풀 수 있다.

(합의 크기가 int범위를 넘어갈 수 있는 것에 주의)

#include <iostream>
 
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}
 
int main(void) {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
 
    int testCase;
    std::cin >> testCase;
 
    int len;
    int val[101] = { 0 };
    for(int i = 0; i < testCase; i++) {
        std::cin >> len;
        for(int j = 0; j < len; j++) {
            std::cin >> val[j];
        }
 
        long long sum = 0;
        for(int k = 0;  k < len; k++) {
            for (int u = k + 1; u < len; u++) {
                int divVal = val[k];
                int cur = val[u];
                if(cur < divVal) { swap(&cur, &divVal); }
                while (divVal > 0) {
                    if(cur % divVal == 0) {
                        sum += divVal;
 
                        break;
                    }
//                    int temp = cur / divVal;
 
                    int temp = divVal;
                    divVal = cur % divVal ;
                    cur = temp;
//                    std::cout << cur << "\n";
                }
            }
        }
        std::cout << sum << "\n";
    }
 
    return 0;
}