[백준9613] GCD 합

땅어 2020. 3. 4. 22:02

728x90

문제

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

9613번: GCD 합

문제 양의 정수 n개가 주어졌을 때, 가능한 모든 쌍의 GCD의 합을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n (1 < n ≤ 100)가 주어지고, 다음에는 n개의 수가 주어진다. 입력으로 주어지는 수는 1000000을 넘지 않는다. 출력 각 테스트 케이스마다 가능한 모든 쌍의 GCD의 합을 출력한다. 예제 입

www.acmicpc.net

풀이

이중 반복문을 써서 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)

728x90