[104일차] GCD 합 - 백준 - 9613(python - 유클리드 호제법)

문제 설명

양의 정수 n개가 주어졌을 때, 가능한 모든 쌍의 GCD의 합을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n (1 < n ≤ 100)가 주어지고, 다음에는 n개의 수가 주어진다. 입력으로 주어지는 수는 1,000,000을 넘지 않는다.

 

출력

각 테스트 케이스마다 가능한 모든 쌍의 GCD의 합을 출력한다.

 

예제 입력, 예제 출력

3 4 10 20 30 40 3 7 5 12 3 125 15 25

70 3 35

 

코드 및 설명

########
def gcd(n, m):
  if n % m == 0:
    return m
  else:
    return gcd(m, n%m)

t = int(input())

for i in range(t):  
  n_arr = list(map(int, input().split(" ")))
  answer = 0
  for i in range(1, n_arr[0]):
    for j in range(i+1, n_arr[0]+1):
      answer += gcd(n_arr[i], n_arr[j])
      
  print(answer)

 

이 문제는 GCD 최대 공약수를 구하는 것인데, 그냥 구하는 것이 아니라, [10, 20, 30, 40] 이라는 배열이 있다면,

 

[10, 20] , [10, 30], [10, 40] 이런식으로 중복되지 않는 경우의 수를 구해서 GCD의 합을 구하는 문제이다.

 

이중 for으로 중복되지않는 경우의 수를 뽑아내면서, gcd 함수로 보내고 값을 리턴 받은 후 answer에 더 해주면

 

해당 값이 나오게 된다.