알고리즘(C++) / 백준 9613 : GCD 합

9613

boj.kr/9613

9613번: GCD 합

 

문제

양의 정수 n개가 주어졌을 때, 가능한 모든 쌍의 GCD의 합을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n (1 < n ≤ 100)가 주어지고, 다음에는 n개의 수가 주어진다. 입력으로 주어지는 수는 1,000,000을 넘지 않는다.

 

출력

각 테스트 케이스마다 가능한 모든 쌍의 GCD의 합을 출력한다.

 

코드

//9613 GCD 합
#include <iostream>
using namespace std;

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

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

	int t, n, num;
	long long sum;
	int arr[101];

	cin >> t;

	for (int i = 0; i < t; i++) {
		cin >> n;
		sum = 0;
		for (int j = 0; j < n; j++) {
			cin >> arr[j];
			for (int k = 0; k < j; k++) {
				sum += GCD(arr[k], arr[j]);
			}
		}

		cout << sum << "\n";
	}
	return 0;
}

 

설명

수를 입력받으면 전에 입력받았던 수들과 비교하여 최대 공약수를 구한 후 sum에 모두 저장하여 출력할 수 있다.

이때, sum은 long long 형이어야한다. 

 

결과

 

난이도

◐○○○○