[C++] 백준 9613번 : GCD 합 (S3)

#문제

www.acmicpc.net/problem/9613

9613번: GCD 합

#풀이 & 학습한 내용

유클리드 호제법으로 각각의 경우에 대해 GCD를 구해서 모두 더해준다. gcd(a,b)=gcd(b,a%b)에서 항상 a>b인 경우로 인자를 전달해줘야 한다고 생각했는데 상관없었다. 만약 a<b라면 gcd(a,b)=gcd(b,a)로 자동으로 바뀐다.

 

#소스코드

#include<iostream>
#include<algorithm>
 
using namespace std;
int arr[102];
 
int gcd(int a, int b) {
    if (b == 0)
        return a;
    else
        return gcd(b, a%b);
}
 
int main(void) {
    int T, N;
    long long ans = 0;
    cin >> T;
 
    while (T--) {
        ans = 0;
        cin >> N;
        for (int i = 1; i <= N; i++) {
            cin >> arr[i];
        }
        for (int i = 1; i <= N-1; i++) {
            for (int j = i+1; j <= N; j++) {
                    ans += gcd(arr[i], arr[j]);
            }
        }
        cout << ans << '\n';
    }
 
}

 

github.com/HoYoungChun/BOJ_algorithm/blob/master/Math/BOJ_9613.cpp

HoYoungChun/BOJ_algorithm