[BOJ] 9613 / GCD 합 / Python 파이썬

[BOJ] 9613 / GCD 합 / Python 파이썬

[BOJ] 9613 / GCD 합 / Python 파이썬

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

9613번: GCD 합

 

풀이

N 개 정수의 정수쌍 조합을 구하고, 그 쌍들의 최대 공약수 합을 구하는 문제이다.

 

combinations 과 gcd method 를 이용해서 구하였다.

 

import sys
from itertools import combinations
import math

T = int(sys.stdin.readline())

for _ in range(T):
    nums = list(map(int, sys.stdin.readline().split()))
    combi = list(combinations(nums[1:], 2))
    res = 0
    for com in combi:
        res += math.gcd(com[0], com[1])

    print(res)