[9613번] GCD 합

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. GCD :: http://www.crocus.co.kr/578

O(n^2)으로 모든 값을 돌며 GCD의 합을 구한 후 결과를 도출하면 된다.

이때 GCD의 합을 구하다보면 결국 int형을 벗어 날 수 있는 케이스가 있음을 조심하자.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <vector>
 
using namespace std;
 
typedef long long ll;
 
int gcd(int a, int b) { return !b ? a : gcd(b, a%b); }
 
int main()
{
    int tc;
    scanf("%d", &tc);
 
    while (tc--)
    {
        int n;
        scanf("%d", &n);
 
        vector<int> vc(n);
 
        for (int i = 0; i < n; i++)
            scanf("%d", &vc[i]);
 
        ll ans = 0;
        for (int i = 0; i < n - 1; i++)
            for (int j = i + 1; j < n; j++)
                ans += gcd(vc[i], vc[j]);
 
        printf("%lld\n", ans);
    }
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>