[🥈3 / 백준 9613 / 파이썬] GCD 합

 

9613번: GCD 합

 

문제

양의 정수 n개가 주어졌을 때, 가능한 모든 쌍의 GCD의 합을 구하는 프로그램을 작성하시오.

입력

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

출력

각 테스트 케이스마다 가능한 모든 쌍의 GCD의 합을 출력한다.

 

예제 입력  3 4 10 20 30 40 3 7 5 12 3 125 15 25

예제 출력  70 3 35

 

풀이

 

GCD(Greatest Common Divisor)란 최대공약수를 의미한다.

테스트 케이스마다 주어진 수로 만들 수 있는 모든 쌍의 최대공약수를 구한 뒤, 이를 다 더한 것을 출력하면 된다.

 

두 가지의 수로만 만들 것이므로 이중 for문으로 모든 쌍을 구할 수 있다.

파이썬의 경우 math 모듈에서 사용 가능한 gcd 함수로 최대공약수를 쉽게 구할 수 있다.

 

import sys,math
input = sys.stdin.readline

for _ in range(int(input())):
    a = list(map(int,input().split()))
    n,nums,r = a[0],a[1:],0
    
    for i in range(n-1):
        for j in range(i+1,n):
            r += math.gcd(nums[i],nums[j])
    print(r)

 

math 모듈 대신 유클리드 호제법을 이용하는 방법도 있다.

유클리드 호제법은 아래 포스팅에 자세히 기술되어 있다.

 

[🥈5 / 백준 1934 / 파이썬] 최소공배수 (유클리드 알고리즘)

 

import sys,math
input = sys.stdin.readline

def gcd(n1,n2):
    while(True):
        r = n2 % n1
        if r == 0:
            return n1
        n2 = n1; n1 = r

for _ in range(int(input())):
    a = list(map(int,input().split()))
    n,nums,r = a[0],a[1:],0
    
    for i in range(n-1):
        for j in range(i+1,n):
            r += gcd(nums[i],nums[j])
    print(r)