[백준] 수학 9613번: GCD 합

문제

양의 정수 n개가 주어졌을 때, 가능한 모든 쌍의 GCD의 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n (1 < n ≤ 100)가 주어지고, 다음에는 n개의 수가 주어진다. 입력으로 주어지는 수는 1,000,000을 넘지 않는다.

출력

각 테스트 케이스마다 가능한 모든 쌍의 GCD의 합을 출력한다.

Approach

사용 알고리즘: 유클리드 호제법

• 각 테스트 케이스마다 주어지는 수들을 배열에 저장하고 이중 for문을 이용해 가능한 모든 쌍에 대해 유클리드 호제법을 이용해서 gcd를 구해준 뒤 결괏값을 갱신한다
• n제곱의 시간복잡도

Source Code

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <string>
#include <sstream>
#include <math.h>
using namespace std;

// 유클리드 호제법 
int GCD(int x, int y)
{
    if (y == 0)
        return x;
    return GCD(y, x % y);
}


int main()
{
    int T;
    cin >> T;
    
    // 각 테스트 케이스 마다
    for (int i = 0; i < T; i++)
    {
        int n; // n 입력받기
        cin >> n;
        
        vector<int> vec;
        
        // 주어진 수들 배열에 저장
        for (int j = 0; j < n; j++)
        {
            int x;
            cin >> x;
            vec.push_back(x);
        }
        
        long long int result = 0; // 결과를 담을 변수
        
        // 모든 쌍에 대해 gcd구해서 결과 갱신
        for (int a = 0; a < (n-1); a++)
        {
            for (int b = a + 1; b < n; b++)
            {
                result += GCD(vec[a], vec[b]);
            }
        }
        
        cout << result << '\n'; // 답안 출력
        
    }
    
    return 0;
}