[백준/Python3] 9613 GCD 합

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

풀이

유클리드 호제법을 이용해 GCD를 구하는 간단한 문제다. 입력이 최대 100개가 들어올 수 있으므로 sys.stdin을 사용.

코드

import sys 

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

for _ in range(int(input())):
    n, *nums = map(int, sys.stdin.readline().split())
    sum_gcd = 0

    for i in range(n - 1):
        for j in range(i + 1, n):
            a, b = nums[i], nums[j]
            sum_gcd = sum_gcd + gcd(a, b)
    
    print(sum_gcd)