[백준 9613번] GCD 합

문제 보기

이 문제는 수학 문제이다.

최대 공약수를 활용한 문제인데, 최대 공약수를 구하는 부분은 math 모듈의 gcd 메소드를 사용하였다.

 

문제를 푼 로직은 다음과 같다.

1. 숫자의 개수와 숫자들을 입력받는다. (6~7번째 줄)
2. 주어진 숫자의 모든 경우의 수에 대해서 최대 공약수를 구하고, 이 최대공약수들의 합을 구해야 하기 때문에 answer 변수에 더해준다. (9~13번째 줄)
3. 주어진 테스트 케이스만큼 실행한다. (4~5번째 줄)

 

import sys
from math import gcd

t = int(sys.stdin.readline())
for _ in range(t):
	line = list(map(int, sys.stdin.readline().split()))
	n, numbers = line[0], line[1:]
	
	answer = 0
	for i in range(n - 1):
		for j in range(i + 1, n):
			answer += gcd(numbers[i], numbers[j])
	print(answer)