(4) [C++, Java] 백준 No.9613 : GCD 합

문제

풀이

자세한 풀이 : 

 

- N개의 수가 주어지면 2개씩 짝지어서 각각의 GCD를 구하여 모두 더하는 문제
- n이 1 ~ 100의 범위이고, n개의 수의 범위는 1 ~ 1,000,000인데,
   n개인 수들을 2개씩 짝지어 만드는 모든 경우의 수는 n(n-1) / 2 이다.
   그러면 이 짝에서 n(n-1) / 2개의 최대공약수들이 나오는데 그 수는 1 ~ 1,000,000의 범위를 가지므로
   총 합의 최대범위는 100*99 / 2 * 1,000,000 = 4,950,000,000(49억)이다.
   이는 int형의 표현범위 +-21억 을 넘고, unsigned int형의 표현범위 +42억을 넘어서는 값으로
   long long 형을 사용해야 한다.(long long 형의 저장범위는 +-900경)

 

# C++

#include <iostream>
#include <vector>

using namespace std;

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

int main()
{
    int T;
    cin >> T;

    for (int test_case = 0; test_case < T; test_case++)
    {
        int n;
        cin >> n;

        // 크기가 n인 벡터 생성 및 숫자들 입력받기
        vector<int> nums_vec(n);
        for (int i = 0; i < nums_vec.size(); i++)
            cin >> nums_vec[i];

        long long sum = 0;                                 // 자료형에 주의!!
        for (int i = 0; i < nums_vec.size()-1; i++)
            for (int j = i+1; j < nums_vec.size(); j++)
                sum += getGCD(nums_vec[i], nums_vec[j]);   // 최대공약수 : 유클리드 호제법 사용

        cout << sum << endl;
    }
}

# Java

import java.util.*;

public class Main {
    public static int gcd(int x, int y) {
        if (y == 0) {
            return x;
        } else {
            return gcd(y, x%y);
        }
    }
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            int n = sc.nextInt();
            int[] a = new int[n];
            for (int i=0; i<n; i++) {
                a[i] = sc.nextInt();
            }
            long ans = 0;
            for (int i=0; i<n-1; i++) {
                for (int j=i+1; j<n; j++) {
                    ans += gcd(a[i], a[j]);
                }
            }
            System.out.println(ans);
        }
    }
}