[lv3] 9613. GCD 합(Python 파이썬 풀이, 유클리드 호제법)

출처

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

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

해석

문제에서 요구하는 것은 리스트 값들 중에서 2개씩을 골라서 최대 공약수들을 합하는 것이다. 그러면 최대 공약수를 어떻게 구할 것인가를 생각해 보아야 한다. 두 수중에서 작은 값을 기준으로 1부터 그 값에 도달할 때까지 두 수가 나눠 떨어지는 값이 있는지 확인하는 방법이 있지만 입력으로 주어지는 수는 최대 1,000,000이므로 10⁶을 매번 확인할 수는 없다. 그래서 최대 공약수를 빠르게 계사는 방법이 유클리드 호제법이다.
유클리드 호제법이란 a와 b의 최대 공약수는 (a가 더 큰 값), a와 b를 a로 나눴을 때 남은 나머지 값의 최대 공약수와 같다는 것을 이용한 것이다. 이를 증명해 보자

유클리드 호제법 증명

두 자연수 A와 B는 최대공약수 G를 갖고 있다고 가정하자. 그러면 A = Ga, B = Gb (a와 b는 서로소 관계)로 나타낼 수 있다. 또한 A는 B로 나눈 값으로 표현하여 A = mB + r 로도 나타낼 수 있다.(m은 몫, r은 B로 나눈 나머지 값이다.) 그러면 여기에 각각을 대입하게 되면 Ga = Gmb + r로 나타낼 수 있게 되어 r = G(a-mb)로 표현할 수 있다.
A와 B의 최대 공약수는 G라고 하였다. 그러면 B와 r 즉, b와 a-mb가 서로소 관계여야 B와 r의 최대 공약수도 G라고 할 수 있다.
만약 b 와 a-mb가 서로소 관계가 아니라면 b = tc, a-mb = td로 나타낼 수 있다. (t는 둘 관계의 최대 공약수이고, c와 d는 서로소 관계)
a-mb = td
a = mb + td = mtc + td = t(mc+d)
즉, a와 b가 t라는 공약수를 갖게 된다. 이전에 a와 b는 서로소 관계라고 하였는데 모순이 생겼다. 만약 t값이 1이라고 하여도 b = c, d = a-mb 가 되어서 b와 a-mb가 서로소 관계가 되어 조건에 모순이 되었다. 그러므로 B와 r의 공약수 또한 G가 된다.

이런식으로 하여 나머지가 0으로 떨어질 때까지 재귀를 통하여 풀면 된다.

소스 코드

import sys
 
def gcd(a, b):
    if not b:
        return a
    return gcd(b, a%b)
 
for _ in range(int(sys.stdin.readline())):
    li = list(map(int, sys.stdin.readline().strip().split()))
    c = li[0]
    li = sorted(li[1:], key=lambda x:-x)
    answer = 0
    for i in range(c-1):
        for j in range(i+1, c):
            answer += gcd(li[i], li[j])
    print(answer)