[백준 C++] 9613 GCD합

문제

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

입력

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

출력

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

풀이

먼저 최대공약수를 구하는 가장 쉬운방법인

유클리드 호제법을 이용한다.

int GCD(int a, int b){
	int temp;
    while(b != 0){
    	temp = a % b;
        a = b;
        b = temp;
    }
    return a;
}

여기서 a, b대소관계 상관없다.
또 눈여결볼점은 GCD를 구할 n의갯수는 최대 100이니, 이경우 n(n-1)/2 이며, 입력으로주어지는수가 100만이므로= > 5099백만 => 약49억인데, int의범위는 +- 21억이고, unsigned int가 + 42억이므로, long long(+-900경) 을 사용해야한다.

문제는 printf에서 long long형은 %lld 로출력해야한다.

long, long long, double, long double출력용 서식문자

long => %ld
unsigned int => %u
long double => %lf
double => %e %E

아래는 전체 코드이다.

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

int GCD(int a, int b) {
	int temp;
	while (b != 0) {
		temp = a % b;
		a = b;
		b = temp;
	}
	return a;
}

int main(void) {
	int t = 0;
	scanf("%d", &t);

	while (t--) {
		int n = 0;
		scanf("%d", &n);
		int* numbers = new int[n];
		for (int i = 0; i < n; i++)
			scanf("%d", &numbers[i]);
		long long res = 0;
		for (int i = 0; i < n - 1; i++)
			for (int j = i + 1; j < n; j++) {
				res += GCD(numbers[i], numbers[j]);
			}
		printf("%lld\n", res);
	}
	return 0;
}