[백준 9613] GCD 합

문제 링크 : https://www.acmicpc.net/problem/9613

9613번: GCD 합

사용 알고리즘:

gcd

 

gcd 알고리즘만 알고 있다면 풀 수 있는 간단한 문제이다.

 

주의할 점은 gcd합이 int범위를 넘어갈 수 있기 때문에 long long으로 선언해줘야 한다는 것이다.

 

 

 

두 값이 모두 1,000,000일 경우 GCD도 1,000,000이 된다.

 

이러한 쌍이 최악의 경우 100*99/2개 만큼 존재할 수 있으므로 거뜬히 int범위를 벗어난다.

 

---

 

그 외의 코드는 간단하다.

 

#include <iostream>
#define n_ 200
using namespace std;

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

int main(void) {
	int T, n;
	int arr[n_];
	cin >> T;
	while (T--) {
		scanf("%d", &n);
		for (int i = 0; i < n; i++) {
			scanf("%d", arr + i);
		}

		long long res = 0;
		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				res += gcd(arr[i], arr[j]);
			}
		}
		printf("%lld\n", res);
	}
}