백준 9613 - GCD 합 [파이썬]

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

9613번: GCD 합

 

풀이 과정

문제에서 시킨대로 주어진 입력의 모든 쌍을 구해 각 쌍의 GCD를 더해주면 된다

10, 20, 30, 40이 입력으로 들어왔다면 (10, 20), (10, 30), (10, 40), (20, 30), (20, 40), (30, 40)이 입력의 모든 쌍일 것이고 각 쌍의 GCD는 10, 10, 10, 10, 20, 10일테니 답은 70이 나올 것이다.

 

소스 코드

import sys


def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)


t = int(sys.stdin.readline())
for _ in range(t):
    n = list(map(int, sys.stdin.readline().split()))
    sumNumber = 0
    for i in range(1, n[0] + 1):
        for j in range(i+1, n[0] + 1):
            sumNumber += gcd(n[i], n[j])
    print(sumNumber)