[BEAKJOON] 백준 9613번 : GCD 합, 파이썬 Python

공부/백준\BeakJoon

[BEAKJOON] 백준 9613번 : GCD 합, 파이썬 Python

na0-0 2023. 7. 22. 21:54

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

9613번: GCD 합

첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n (1 < n ≤ 100)가 주어지고, 다음에는 n개의 수가 주어진

www.acmicpc.net

문제

유클리드 호제법을 사용하면, 아주 간단하게 풀린다.

정답 코드

def GDB(a, b):
    while(b>0):
        a, b = b, a%b
    return a
    

num = int(input())

while(num):
    num -= 1
    list_num = list(map(int, input().split()))
    count = 0
    for i in range(1, list_num[0]):
        for j in range(i+1, list_num[0]+1):
            count += GDB(list_num[i], list_num[j])
    print(count)