9613번 : GCD 합 - Python

문제

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

풀이

유클리드 호제법으로 모든 경우의 GCD(최대공약수)를 구한다.

코드

from sys import stdin

input = stdin.readline

def gcd(a, b):
    if b>a:
        a, b = b, a

    while b!=0:
        a = a%b
        a, b = b, a

    return a

n = int(input())

for i in range(n):
    array = list(map(int,input().split()))
    cnt = 0

    for j in range(1,array[0]+1): #모든 경우의 수를 거친다.
        for k in range(j+1,array[0]+1): 
            cnt += gcd(array[j],array[k])

    print(cnt)