백준 9613 : GCD 합

★★☆☆☆

문제가 무슨 말인지를 이해하는 데에 조금 걸렸지만, 이해하니까 쉬운 문제였다.
O(n^3)라서 시간 초과 걸릴까봐 걱정했는데 그러진않았다

<나의 풀이>

그냥 두 개의 숫자의 gcd를 계속해서 더해주면 되는 문제
유클리드 호제법을 그대로 사용했다.

#include <iostream>
using namespace std;

int gcd(int a, int b) {
	int r;
	while (b != 0) {
		r = a % b;
		a = b;
		b = r;
	}
	return a;
}


int main() {
	int t, n;
	cin >> t;
	

	for (int i = 0; i < t; i++) {
		cin >> n;
		int arr[100];
		long long ret=0;
		for (int j = 0; j < n; j++) {
			cin >> arr[j];
		}
		for (int j = 0; j < n; j++) {
			for (int k = j+1; k < n; k++) {
				ret += gcd(arr[j], arr[k]);
				//cout << j << "와 " << k << "사이의 gcd :: " << gcd(arr[j], arr[k])<<"\n";
			}
		}
		cout << ret<<"\n";
	}
}