백준 / 수학 / 9613번 / GCD합 / C++

문제

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

입력

첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 

각 테스트 케이스는 수의 개수 n (1 < n ≤ 100)가 주어지고, 다음에는 n개의 수가 주어진다.

입력으로 주어지는 수는 1,000,000을 넘지 않는다.

출력

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

예제 입력 1 

3

4 10 20 30 40

3 7 5 12

3 125 15 25

예제 출력 1 

70

3

35

 

#include <iostream>
using namespace std;

int gcd(int a, int b) {
	return b ? gcd(b, (a % b)) : a;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int t;
	cin >> t;
	
	while(t--) {
		long long result = 0;
		int n;
		cin >> n;
		int arr[n];
		
		for(int i=0; i<n; i++) {
			int num;
			cin >> num;
			arr[i] = num;
		}
		
		for(int i=0; i<n; i++) {
			for(int j=i+1; j<n; j++) {
				result += gcd(arr[i], arr[j]);
			}
		}
		
		cout << result << '\n';
	}
		
	return 0;
}

---

gcd = 최대공약수이다.

이번문제는 한가지만 조심하면 매우 간단한 문제였다.

 

일단 최대공약수 구하는 알고리즘에 대한 설명은 이전의 포스팅에 있으므로 밑의 포스팅을 참고바란다.

(유클리드 호제법을 이용했다.)

2021.08.01 - [ALGORITHM/백준] - 백준 / 수학 / 2609번 / 최대공약수와 최소공배수 / C++

백준 / 수학 / 2609번 / 최대공약수와 최소공배수 / C++

 

혹시나해서 문제 이해를 돕자면,

예제 입력의 3 7 5 12 는 3개의 수 7, 5, 12를 받겠다는 것이다.

그리고 7, 5, 12에서 가능한 모든 두 수로 이루어진 한쌍에서 최대공약수를 구한뒤 다 더해주면 된다.

위의 입력에서 가능한 모든 쌍은 (7, 5), (7, 12), (5, 12) 이고, 각각의 최대공약수는 1, 1, 1 이므로 다 더해주면 3이된다.

 

위에서 말한 한가지 조심할것은 최대공약수의 합을 받는 변수(위의 코드에선 result)를

int 타입으로 지정해주면 안된다는것이다.

 

문제에서 보면 각 최대 케이스의 개수는 100개이고 각각 수의 최대 입력값이 100만이라서

만약 입력으로 케이스의 개수가 100개가 들어왔다고 하면 100개에서 2개의 수를 고르는 가짓수는,

100C2 일것이고, 100! / (2! * 98!) 이 되어 100 * 49 = 4900이 될것이다.

그럼 총 4900쌍의 최대공약수를 더해야하는데 이마저도 최대 입력값 100만이 들어왔을경우,

100만과 100만의 최대공약수는 100만이기 때문에 100만 * 4900은 49억으로 int의 범위를 두 배 이상 넘어선다.

 

따라서 long long 으로 설정해 주어야 하는것만 조심해주면 될 것 같다.