백준 9613 GCD 합

작성일 | In |

Problem : GCD 합

유형 : 수학

문제 설명

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

예제 입력

1
2
3
4
3
4 10 20 30 40
3 7 5 12
3 125 15 25

예제 출력

1
2
3
70
3
35

해결 전략

유클리드 호제법을 통해 gcd를 구한다. 라이브러리 안의 gcd 함수를 이용했다.

주의할 점

  • gcd 함수는 numeric 헤더 안에 있다.

풀이

숫자를 입력받고 수들의 최대 공약수를 구한다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
#define ll long long
using namespace std;

int t;

ll solve(int n) {
    int arr[101] = { 0 };
    ll sum = 0;
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }

    for (int i = 0; i < n; ++i) {
        for (int ii = i + 1; ii < n; ++ii) {
            sum += gcd(arr[i], arr[ii]);
        }
    }
    return sum;
}


void input() {
    cin >> t;
    int n;
    while (t--) {
        cin >> n;
        cout << solve(n) << "\n";
    }
}


int main()
{
    ios_base::sync_with_stdio(false);
    //freopen("input.txt", "r", stdin);
    cin.tie(NULL);  cout.tie(NULL);
    input();

    return 0;
}

피드백

없음