[BOJ/Silver 3] 백준 9613 GCD 합(C++)

문제 링크

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

9613번: GCD 합

 

문제

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

입력

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

출력

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

예제 입력 1

3
4 10 20 30 40
3 7 5 12
3 125 15 25

예제 출력 1

70
3
35

알고리즘 분류

• 수학

풀이

각 테스트 케이스마다 (N * (N-1)) / 2개의 순서쌍의 최대공약수의 합을 구해주면 끝이다.

N개의 수를 받은 후 내림차순 정렬을 해주면 편하다.

코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define LL long long

using namespace std;
int T;
int N;
vector<LL> Vec;
LL Answer;

void Init() {
	Vec.clear();
	Answer = 0;
}

LL GCD(LL N, LL M) {
	while (1) {
		LL R = N % M;
		if (R == 0) {
			return M;
		}
		N = M;
		M = R;
	};
}

void Settings() {
	sort(Vec.begin(), Vec.end(), greater<int>());
	for (int i = 0; i < Vec.size(); i++) {
		for (int j = (i + 1); j < Vec.size(); j++) {
			Answer += GCD(Vec[i], Vec[j]);
		}
	}
}

void Find_Answer() {
	cout << Answer << "\n";
}

void Input() {
	cin >> T;
	while (T--) {
		Init();
		cin >> N;
		for (int i = 0; i < N; i++) {
			LL I;
			cin >> I;
			Vec.push_back(I);
		}
		Settings();
		Find_Answer();
	};
}

int main() {
	FASTIO
	Input();

	return 0;
}