[백준] 9613번 : GCD 합 (Python)

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

 

정수 N개가 주어졌을 때,

가능한 모든 쌍의 GCD의 합을 구하는 문제다.

import sys

# 유클리드 호제법으로 최대공약수 구하기
def gcd(N, M):
    
    if(M == 0):
        return N
    
    return gcd(M, N%M)

input = sys.stdin.readline
T = int(input())
    
for _ in range(T):
    N, *case = list(map(int, input().split())) # N
    
    answer = 0
    
    for i in range(N):
        for j in range(i+1, N):
            answer += gcd(case[i], case[j]) # 모든 쌍의 gcd 구하기
            
    print(answer)

 

 

[문제풀이]

---

 

 

테스트 케이스의 수를 입력받고, 각 테스트 케이스마다 수의 개수 N개와 N개의 수를 입력받는다.

그 후 모든 쌍의 gcd를 유클리드 호제법으로 구하고, 그 값을 더하면 끝!