[C++] 백준 9613번 GCD 합

각 수에대한 모든 최대공약수의 합을 구하는 문제입니다.

최대공약수를 구하는 함수입니다.

int gcd(int a, int b)
{
	if (b == 0) {
		return a;
	}
	else {
		return gcd(b, a % b);
	}
}

 

각 수에 대해 최대공약수를 구하는 함수에 대입하여
추출된 수들을 전부 더해줘서 출력해주었습니다.

 

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
using namespace std;

int gcd(int a, int b)
{
	if (b == 0) {
		return a;
	}
	else {
		return gcd(b, a % b);
	}
}

int main(int argc, char *argv[])
{
	int ts;
	int n;
	int num;
	long long result;
	vector<int> v;

	cin >> ts;

	while (ts--) {
		result = 0;

		cin >> n;

		for (int i = 0; i < n; ++i) {
			cin >> num;
			v.push_back(num);
		}

		for (int i = 0; i < n; ++i) {
			for (int j = i + 1; j < n; ++j) {
				result += gcd(v[i], v[j]);
			}
		}
		v.clear();
		cout << result << endl;
	}	

	return 0;
}