백준 9613번 GCD 합 // C++

문제

 

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

입력

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

출력

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

 

---

 

풀이

 

입력받은 모든 수의 최대공약수의 합을 구하는 문제이다.

 

최대공약수는 유클리드 호제법을 사용하여 구하면 된다!

 

---

 

코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int findGCD(int num1, int num2) {
	if (num1 < num2)
		swap(num1, num2);

	if (num2 == 0)
		return num1;

	return findGCD(num2, num1 % num2);
}

int main() {
	int test_case;

	cin >> test_case;

	for (int t = 0; t < test_case; t++) {
		int n, input;

		cin >> n;
		vector<int> num;
		long long sum = 0;

		for (int i = 0; i < n; i++) {
			cin >> input;

			num.push_back(input);
		}

		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				sum += findGCD(num[i], num[j]);
			}
		}

		cout << sum << "\n";
	}

	return 0;
}