[백준 C++] 9613번: GCD 합

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

9613번: GCD 합

 

GCD가 뭔지 몰라서 검색해본결과 최대 공약수를 의미한다고 한다.

 

각 테스트 케이스 마다 가능한 최대 공약수의 합을 구하면 되는문제

 

문제를 이해하는 시간이 조금 걸린편

 

예를들어 입력이

 

1

3 10 20 30 40 이렇게 주어졌다면

 

10과 20의 최대공약수 + 10과 30, 10 40, 20 30, 20 40, 30 40 이렇게 총 4C2  = 6개의 최대공약수를 구해서 더해준 값을 출력해주면 된다.

 

함수를 만들고, 자료형에 주의해서 작성하자 입력으로 주어지는 수의 최대값이 100개까지 인데 범위는 백만이므로 100C2 * 백만을 구하면 99*50*백만 = 49억이다. int형의 표현범위는 +-21억이며, unsigned int 또한 +42억이므로 이를 넘는 범위인 long long 형으로 선언해줍니다. (long long의 표현범위는 +-900경이다.)

 

함수는 인터넷에서 찾은 gcd공식을 찾아서 사용하였다.

 

#include <iostream>
 
using namespace std;
 
int gcd(int x, int y)
{
	if (x % y == 0) return y;
	else return gcd(y, x % y);
}
 
int main() {
	int t;
	int n;
	long long a[101] = { 0, };
	
	cin >> t;
 
	for (int test_case = 0; test_case < t;test_case++) {
		long long sum = 0;
		cin >> n;
		for (int i = 0;i < n;i++) {
			cin >> a[i];
		}
 
		for (int i = 0;i < n;i++) {
			for (int j = i + 1;j < n;j++) {
				sum += gcd(a[i], a[j]);
			}
		}
		cout << sum << "\n";
	}
 
 
	return 0;
}

 

for 문 안에있는 j를 i로 잘못써서 1시간 동안 찾았다...진짜 이런게 코딩의 묘미라는 생각이든다.