[C++] 백준 알고리즘 9613 GCD 합 (유클리드 호제법)

GCD(Greatest Common Divisor)

GCD란 최대공약수를 의미한다.

 

최대공약수를 구할 땐 유클리드 호제법을 이용하는게 편하다. 유클리드 호제법이란, a b의 최대공약수가 a%b(나머지) b의 최대공약수가 같다는 것을 이용하는 것이다.

---

예를 들어 15와 10이 있다고 해보자.

a=15, b=10이라고 하면 a%b=5, b=10이 된다.

이 a%b값을 a에 대입하자.

 

x%y를 할 때에는 x>y여야하므로

둘의 자리를 바꿔줘야한다

 

그러면 a=10, b=5가 된다.

나머지가 0이 될 때까지 해보자.

 

a%b=5, b=5가 된다. 

a%b를 a에 대입하면

a=5, b=5가 되고

a%b = 0이 된다.

 

0이 되면 작은 값인 b를 리턴한다.

그러면 최대공약수가 b값, 즉 5가 된다

---

예를 들어 7과 3이 있다고 해보자

a=7, b=3이다.

a%b=1, b=3이다.

 

a%b를 a에 대입해주면 a=1, b=3이다.

a값이 더 커야하므로 둘의 자리를 바꿔주면 a=3, b=1이다.

a%b를 해주면 0이다. 3나누기 1은 몫이 3, 나머지가 0이다.

a%b=0이라면 이때 b 값이 GCD다. 즉 1이 최대공약수가 된다.

---

이 문제는 sum의 범위도 유심히 봐야한다.

n개를 입력했을 때 우리는 2개씩 짝지어 최대공약수를 구해야한다.

 

순서에 상관없이 2개씩 짝짓는다고 하면

nC2, 즉 n(n-1)/2만큼의 최대공약수를 구해야한다.

 

n의 1000000개까지 가능하기때문에

이를 고려하면 sum의 값은 어마무시하게 커진다.

그러므로 sum을 int가 아닌 long long을 사용해 선언해야한다.

9613

#include<iostream>
#include<vector>

using namespace std;

//유클리드 호제법
//a,b의 최대공약수는 a%b, b의 최대공약수와 같다
//x%y 시 크기가 x>y여야 하므로
//a%b와 b의 자리를 바꿔 return gcd(b, a%b)를 한다.
int gcd(int a, int b) {
	if (a % b == 0) return b;
	else return gcd(b, a % b);
}

int main() {
	int t;
	cin >> t ;	
	
	while (t--) {
		vector<int> v;
		//n개의 수를 2개씩 짝이어 gcd를 구하면
		// n(n-1)/2 개가 나옴
		// 한 n이 1000000범위이므로
		//gcd의 합인 sum은 long long 이어야한다.
		long long sum = 0;

		int n;
		cin >> n;
		int temp = n;

		int k;
		while (temp--) {
			cin >> k;
			v.push_back(k);	
		}

		for (int i = 0; i < n; i++) {
			for (int j = i+1; j < n; j++) {
				sum += gcd(v[i], v[j]);
			}
		}

		cout << sum << '\n';
	}
}