Math12서로소 평균(21920)

문제

효성이는 길이가 $N$인 수열 $A$에서 $X$와 서로소인 수들을 골라 평균을 구해보려고 한다.

효성이를 도와 이를 계산해주자.

입력

첫 번째 줄에 입력될 수들의 개수 N이 주어진다. $(2 < N < 500,000) 

두 번째 줄에는 수열 A를 이루는 자연수 A, 가 공백으로 구분되어 주어진다. (2 <= A <= 1,000,000)$

수열 A에 X와 서로소인 수가 최소 1개 이상 존재한다.

마지막 줄에는 X가 주어진다. (2 <= X <= 1,000,000) 

출력

첫째 줄에 수열 A에서 X와 서로소인 수들의 평균을 출력한다.

절대/상대 오차는 10-6까지 허용한다.

풀이

• 유클리드 호제법 또는 python Math 라이브러리에서 gcd 함수 활용

코드

import sys

def input():
    return sys.stdin.readline().rstrip()

def GCD(x,y):
    if y == 0:
        return x
    else:
        return GCD(y, x%y)

N = int(input())
A = list(map(int, input().split()))
X = int(input())
ans = []
for i in A:
    if GCD(X,i) == 1:
        ans.append(i)
print(sum(ans)/len(ans))

배운 것

유클리드 호제법을 사용하여 서로소를 구할 수 있었다.
즉 최대공약수를 구하는 방법인 gcd 가. 즉 최대 공약수가 1인 경우에 서로소라고 할 수 있다.
3 과 4의 최대공약수가 1인 것처럼.

코멘트