BOJ 9613 GCD 합

https://www.acmicpc.net/problem/9613
시간 1초, 메모리 128MB
input :

• t (1 ≤ t ≤ 100)
• n (1 < n ≤ 100) n개의 수

output :

• 가능한 모든 쌍의 GCD의 합

---

gcd ?
최대 공약수를 뜻함.

이를 구하려면 어떻게 해야하는가?
1. a > b
2. a를 b로 나머지 연산 (a % b)
-> 재귀 GCD(b, a % b)
3. b가 0이면 a가 최대공약수

아니면 그냥 math 라이브러리 안의 gcd 를 이용하면 그냥 최대 공약수를 리턴해준다.

import sys
from math import gcd

t = int(sys.stdin.readline())
for i in range(t):
    num = list(map(int, sys.stdin.readline().split()))
    ans = 0

    for j in range(1, num[0]):
        for k in range(j + 1, num[0] + 1):
            ans += gcd(num[j], num[k])
    print(ans)