GCD 합 _ 백준 9613

GCD, 즉 최대공약수의 합을 출력하는 문제이다.

---

해당 문제에서는, 테케의 수, 각 테케에서의 숫자 갯수, 테케 내의 숫자 입력 이렇게 세가지로 크게 입력을 나눌 수 있다.

입력을 받은 뒤에는 최대공약수를 다 더하면 되는데, 이는 함수를 통해서 간단히 구현할 수 있다.

 

최대 공약수 관련 문제는 아래에 정리해놓은게 있으니, 그쪽을 보고 오면 좋을 것 같다.

2020/05/16 - [백준 문제풀이] - 최대공약수/ 최소공배수_ 백준 2609번/1934번

사실 gcd 함수만 알면 그렇게 어려운 문제는 아닌 것 같다.

 

#include <iostream>
#include <stdio.h>
using namespace std;
int nums[100];

int gcd(int a, int b)
{
	if (b == 0)
		return a;
	else
		return gcd(b, a % b);
}

int main(void)
{
	int count;
	scanf("%d", &count);
	while (count--)
	{

		int num;
		scanf("%d", &num);
		for (int i = 0; i < num; i++)
		{
			cin >> nums[i];
		}	

		long long sum = 0;
		for (int i = 0; i < num - 1; i++)
		{
			for (int j = i + 1; j < num; j++)
			{
				sum += gcd(nums[i], nums[j]);
			}
		}
		cout << sum << "\n";
	}
	return 0;
}