[백준9613] GCD 합

문제

---

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

9613번: GCD 합

풀이

---

이중 반복문을 써서 2개로 이루어진 숫자의 조합을 생성한 뒤 각각 유클리드 호제법을 적용시켜 gcd를 구하고 이들을 더해준다.

코드

---

def gcd(a,b):

    while b!=0:
        r = a%b
        a = b
        b = r
    return a

if __name__=='__main__':

    trial = int(input())
    for _ in range(trial):
        line = input().split()
        num = line[1:]
        num = [int(i) for i in num]
        sum = 0
        for i in range(int(line[0])-1):
            j=i+1
            while True:
                if j==int(line[0]):
                    break
                sum+=gcd(num[i],num[j])
                j+=1
        print(sum)