9613 : GCD 합

이번에는 유클리드 알고리즘을 적용한 재귀함수를 이용해 최대 공약수를 이용하기로 하였다. 

메인함수내에서 벡터들을 처리하면서, 비효율적으로 처리된것 같긴한데, 이를 어떻게 효율적으로 할진 천천히 생각해봐야겠다.

처음시도에 gcd 합을 담는 sum을 int형을 사용했는데 오답이라 떠서, 입력 조건을 보니, int범위를 넘을듯싶어 long long int 형으로 좀더 범위가 큰 데이터형을 쓰니 정답처리가 되었다.

 

#include <iostream>
#include <vector>

using namespace std;

int max_num(int a, int b) { //최대공약수
	if (b == 0) return a;
	return max_num(b, a%b);
}

int main() {
	int n, n2;
	long long sum=0;
	vector<int> tmp;
	vector<long long> sum2;
	cin >> n;
	for (int i = 0; i < n; i++) {
		sum = 0;
		cin >> n2;
		for (int j = 0; j < n2; j++) {
			int num;
			cin >> num;
			tmp.push_back(num);
		}
		for (int j = 0; j < n2-1; j++) {
			for (int k = j+1; k < n2; k++) {
				sum += max_num(tmp[j], tmp[k]);
			}
		}
		sum2.push_back(sum);
		tmp.clear();
	}
	for (int i = 0; i < sum2.size(); i++) {
		cout << sum2[i] << endl;
	}
	return 0;
}