[BOJ/C++] 9613 GCD 합

문제

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

풀이

유클리드 호제법

정수 a, b (a>=b)
r = a % b

a와 b의 최대공약수 (a, b)
=> (a,b) = (b, r)

a와 b의 최소공배수
=> a * b / (a, b)

코드

#include <iostream>
#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 T;

	cin >> T;
	while (T--) {
		int n;
		vector<int> v;
		long long sum = 0;

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

			cin >> tmp;
			v.push_back(tmp);
		}

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

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

	return 0;
}