(c++)백준 9613번: GCD 합

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

9613번: GCD 합

[풀이]

이중for문으로 원소가 2개인 중복없는 쌍들을 만들 수 있다.

GCD는 유클리드 호제법으로 풀었다. 

72 = 34 * 2 + 4 34 = 4 * 8 + 2 4 = 2 * 2 72, 34의 최대공약수: 2

#include <iostream>
#include <vector>
using namespace std;

int t, n;
int Num[101];//양의 정수 n개 저장
vector<int>Pair;//최대 공약수 구할 쌍
long long gcdSum = 0;

int getGcd(int a, int b) {
	int c;
	while (b != 0) {
		c = a % b;
		a = b;
		b = c;
	}
	return a;
}

void solution() {
	cin >> t;
	while (t--) {
		cin >> n;
		for (int i = 0; i < n; i++) {
			cin >> Num[i];
		}
		for (int i = 0; i < n - 1; i++) {
			for (int j = i + 1; j < n; j++) {
				gcdSum += getGcd(Num[i], Num[j]);
			}
		}
		cout << gcdSum << endl;
		gcdSum = 0;
	}
}

int main() {
	solution();
	return 0;
}