백준 9613 c++

오랜만에 GCD를 구하는 알고리즘을 사용해서 다시 공부하게 되었다. 유클리드 호제법이라 부른다. 첫시도에서는 틀렸는데 그 이유는 1000000과 1000000의 최대 공약수는 1000000이기 때문에 모든 최대공약수의 합은 int를 넘어설 수 있다. 그래서 long long으로 다시 지정해주었다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

long long GCD(int A, int B)
{
	long long temp;

	if (A < B)
	{
		temp = A;
		A = B;
		B = temp;
	}
	while (B != 0)
	{
		temp = A % B;
		A = B;
		B = temp;
	}
	
	return A;
}

long long find_answer(vector<int>& v)
{
	long long sum = 0;
	int i, j;

	for (i = 0; i < v.size() - 1; i++)
	{
		for (j = i + 1; j < v.size(); j++)
		{
			sum += GCD(v[i], v[j]);
		}
	}

	return sum;
}

void input_v(vector<int> &v)
{
	int i;
	int N, temp;
	
	cin >> N;
	for (i = 0; i < N; i++)
	{
		cin >> temp;
		v.push_back(temp);
	}

	return;
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int T;
	int i;

	cin >> T;
	for (i = 0; i < T; i++)
	{
		vector<int> v;

		input_v(v);
		cout << find_answer(v) << "\n";
	}

	return 0;
}