[Baekjoon - 9613] GCD 합

난이도: Silver IV

 

태그

• Euclidean Algorithm → Greatest Common Divisor

 

풀이

1. 풀이

하나의 \( i, j \) 쌍에 대해, \( \text{GCD}(A_{i}, A_{j}) \)는 log 시간에 알아낼 수 있습니다.

 

이러한 쌍이 \( O(N^2) \)개 있으니, 이를 다 돌려주면 됩니다.

 

2. 코드

int gcd(int a, int b){ return b==0 ? a : gcd(b, a%b); }
 
int arr[120];
 
void Main(){
    int t; cin >> t; while (t--){
        int n; cin >> n;
        for (int i = 1; i <= n; i++){ cin >> arr[i]; }
        ll ans = 0;
        for (int i = 1; i <= n; i++){
            for (int j = i+1; j <= n; j++){ ans += gcd(arr[i], arr[j]); }
        }
        cout << ans << endl;
    }
}