[수학] 9613번 GCD 합 C++ 풀이법

 

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

이 문제 역시 유클리드 호제법으로 풀 수 있습니다. 

https://haula.tistory.com/entry/%E3%85%81 <- 여기서 자세한 알고리즘 설명을 확인 하실 수 있습니다.

여기서 주의할 것은 자료형입니다.

입력으로 주어지는 수는 범위가 1,000,000까지 입니다.

총 합의 범위는 10*99/2*1,000,000 이므로 49억입니다.

int형의 표현범위는 +-21억이며, unsigned int형의 표현범위는 +42억입니다.

따라서 이를 넘는 범위인 long long 형으로 선언해야합니다. (long long의 표현범위눈 +-900경입니다.)

#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, n;
    long long n_arr[101] = { 0 };
    long long sum[101] = { 0 };
 
    cin >> t;
 
    for (int i = 0; i < t; i++)
    {
        cin >> n;
        for (int j = 0; j < n; j++)
        {
            cin >> n_arr[j];
        }
        for (int k = 0; k < n; k++)
        {
            for (int p = k + 1; p < n; p++)
            {
                sum[i] += gcd(n_arr[k], n_arr[p]);
            }
        }
    }
 
    for (int i = 0; i < t; i++)
    {
        cout << sum[i]<<"\n";
    }
}

정답확인 완료하였습니다.