Baekjoon

Baekjoon 9613번 GCD 합

ppwag 2020. 11. 23. 13:00

문제

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

걸린 시간

00 : 08 : 57

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
#define all(c) c.begin(), c.end()
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tc;
    cin >> tc;
    while(tc--){
        int n;
        cin >> n;
        vector<int> num(n);
        for(auto& i : num) cin >> i;
        ll ans = 0;
        for(int i = 0; i < n; i++)
            for(int j = i+1; j < n; j++)
                ans += gcd(num[i], num[j]);
        cout << ans << "\n";
    }
    return 0;
}

쌍의 개수가 100*99/2 = 495,000 개 까지 나올 수 있고 입력으로 주어지는 수가 최대 1,000,000 이므로 합이 int 형 범위를 벗어날 수 있다고 한다.

long long 형 데이터 타입에 모든 쌍의 gcd(최대공약수)를 누적시켜 출력하면 ac 를 받을 수 있다.

'Baekjoon' 카테고리의 다른 글

Baekjoon 7682번 틱택토  (0) 2020.12.03
Baekjoon 1956번 운동  (0) 2020.12.02
Baekjoon 2931번 가스관  (0) 2020.11.23
Baekjoon 16954번 움직이는 미로 탈출  (0) 2020.11.22
Baekjoon 11066번 파일 합치기  (0) 2020.11.22

댓글