백준 9613번 GCD 합

https://www.acmicpc.net/problem/9613

9613번: GCD 합

 

단순히 모든 수의 쌍을 골라서 최대공약수를 유클리드 호제법으로 구하고 더하면 되는 문제이다.

답이 int형 범위를 벗어날 수 있어 long long int를 사용해야 한다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int num[100];

int gcd(int a, int b)
{
	if (!(a % b))
		return b;
	return gcd(b, a % b);
}

int main()
{
	int n, t;
	long long int count;
	scanf("%d", &t);

	for (int i = 1; i <= t; i++)
	{
		scanf("%d", &n);
		count = 0;
		for (int j = 0; j < n; j++)
		{
			scanf("%d", &num[j]);
		}
		for (int j = 0; j < n - 1; j++)
		{
			for (int p = j + 1; p < n; p++)
				count += gcd(num[j], num[p]);
		}
		printf("%lld\n", count);
	}

	return 0;
}