GCD 합 풀이

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

백준 알고리즘 기초 1/2 301에서 1번째 - 9613번 GCD 합을 풀어보았다.

 

풀이: 어렵게 생각하지 말고, 숫자들끼리 gcd를 하나하나 구해 더하면 된다.

 

C++

 

Python

import math

n=int(input())
for i in range(n):
	ts=list(map(int,input().split()))
	sum=0
	for j in range(1,ts[0]+1):
		for k in range(j+1,ts[0]+1):
			sum+=math.gcd(ts[j],ts[k])
	print(sum)

Java