[C++/백준 9613번] GCD 합

 

 

유클리드 호제법을 통한 풀이. 자료형 범위에 주의한다.

 

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

int Euclid(int p, int q)
{
	if (q == 0) return p;
	else return Euclid(q, p % q);
}



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

	int n;
	long long arr[101];
	cin >> n;

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

		for (int j = 0; j < num; j++)
		{
			int input;
			cin >> input;
			arr[j] = input;

		}

		long long cnt = 0;
		
		for (int a = 0; a < num; a++)
		{
			for (int b = a+1; b < num; b++)
			{
				cnt += Euclid(arr[a], arr[b]);
			}
		}

		cout << cnt << '\n';


	}




}