[백준/c++] 9613번 GCD 합

9613번 문제 링크

문제

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

입력

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

출력

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

풀이

여기서 주목해야할 키워드는 모든 쌍의 GCD의 합 입니다.
1,2,3,4 가 있다고 할 때 1,2 / 1,3 / 1,4 / 2,3 / 2,4 / 3,4 총 6종류의 그룹이 만들어져야 합니다.
모든 쌍의 합을 구하려면 첫번째 수 에서 N번째 수 까지 GCD 를 구해서 더하고 두번째 수에서 N 번째 수 까지 GCD 를 구해서 더하는 방식을 사용하면 됩니다.

그리고 수의 개수가 100개고 1,000,000 를 100번 입력하게 되면 int 의 범위인 2,147,483,647 를 넘기 때문에 long long 으로 선언해줘야 한다는 점만 유의하면 됩니다.

소스코드

#include <iostream>
using namespace std;

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

int main() {
    
    int t, n;
    long long count = 0;
    cin >> t;
    
    int arr[100];
    
    for(int i=0;i<t;i++) {
        count = 0;
        cin >> n;
        
        for(int j=0;j<n;j++) {
            cin >> arr[j];
        }
        
        for(int k=0;k<n-1;k++) {
            for(int q = k+1;q<n;q++) {
                count += gcd(arr[k], arr[q]);
            }
        }
        cout << count << endl;
    }
    
    return 0;
}

정답