황소개발자

백준 9613 파이썬 python : GCD 합 @@황소처럼 우직하게@@ 본문

백준 문제 풀이

백준 9613 파이썬 python : GCD 합 @@황소처럼 우직하게@@

hjp845 2020. 2. 27. 03:03
반응형
import sys
import itertools
input = sys.stdin.readline

def gcd(a, b):
    return gcd(b, a % b) if b else a

t = int(input())
for i in range(t):
    num_list = list(map(int, input().split()))
    num_list = num_list[1:]
    ans = 0
    for a, b in itertools.combinations(num_list, 2):
        ans += gcd(a, b)
    print(ans)

gcd의 설명은 아래 글에!

 

백준 2609 파이썬 python : 최대공약수와 최소공배수 @@황소처럼 우직하게@@ [유클리드 호제법 알고리즘][gcd][lcm]

이걸 아직도 파악하지 못하고 있었다니.. 반성한다. 유클리드 호제법은 기원전 300년에 나온 첫번째 알고리즘으로 유명하다. a 를 b로 나눈 나머지를 r 이라고 했을 때, a와 b의 최대공약수는 b와 r의 최대공약수..

hjp845.tistory.com

 

반응형
저작자표시

'백준 문제 풀이' 카테고리의 다른 글

백준 6588 파이썬 python : 골드바흐의 추측 @@황소처럼 우직하게@@ 에레토스테네스의 체 + 최적화  (0) 2020.02.27
백준 1978 파이썬 python : 소수 찾기 @@황소처럼 우직하게@@ 에라토네스의 체  (0) 2020.02.27
백준 1934 파이썬 python : 최소공배수 @@황소처럼 우직하게@@ 숏코딩  (0) 2020.02.27
백준 2609 파이썬 python : 최대공약수와 최소공배수 @@황소처럼 우직하게@@ [유클리드 호제법 알고리즘][gcd][lcm]  (0) 2020.02.27
백준 10430 파이썬 python : 나머지 @@황소처럼 우직하게@@ 이 문제의 알고리즘은 정말 중요하다.. 오버플로우 방지를 위해서인데 [모듈][나머지 연산]  (0) 2020.02.27
'백준 문제 풀이' Related Articles more
Comments