[백준] 9613번 : GCD 합 (C++)

9613번 : GCD 합

---

문제)

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

 

 

 

입력 :

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

 

 

 

출력 :

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

 

 

 

 

 

 

풀이)

 

// 9613. GCD 합
#include <iostream>
#include <vector>
 
using namespace std;
 
int t, n;
vector<int> vec;
 
int get_gcd(int big, int small)
{
    if (small == 0) return big;
    else return get_gcd(small, big % small);
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> t;
 
    while (t--)
    {
        vec.clear();
 
        cin >> n;
        int temp;
        for (int i = 0; i < n; i++)
        {
            cin >> temp;
            vec.push_back(temp);
        }
 
        long long total = 0;
        for (int i = 0; i < n - 1; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                total += get_gcd(vec[i], vec[j]);
            }
        }
 
        cout << total << '\n';
    }
 
    return 0;
}
 

---

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

9613번: GCD 합