[백준][C++] 9613: GCD 합

문제 링크: https://www.acmicpc.net/problem/9613

 

자연수 n개가 주어졌을 때, 가능한 모든 쌍의 GCD 합을 구하는 문제입니다.

간단히 for문 두개로 모든 조합의 gcd를 구하고, 이를 변수에 차곡차곡 더하면 됩니다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

using namespace std;


int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);


	int t;
	cin >> t;
	while (t--) {
		vector<int> v;
		int n;
		long long sum=0;
		cin >> n;
		v.resize(n);
		for (auto& c : v)
			cin >> c;

		for (int i = 0; i < n-1; ++i) {
			for (int j = i + 1; j < n; ++j) {
				sum += gcd(v[i], v[j]);
			}
		}


		cout << sum << '\n';
	}

	return 0;
}

주의해야 할 점이 있는데요, gcd 합의 범위가 int형을 초과할 수 있기 때문에 long long 등의 자료형으로 합을 저장하셔야 합니다.