[python/파이썬] 백준 21920 서로소 평균

문제

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

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

입력

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

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

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

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

출력

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

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

예제 입력 1 복사

5
4 2 8 5 7
4

예제 출력 1 복사

6

 

 

[소스 코드]

 

서로소에 대한 정의는 두 수 사이에 1 말고는 공약수가 없는 것이다.

그리고 서로소인 두 수의 최대공약수는 1이고(공약수가 1밖에 없으니)

최소 공배수가 두 수의 곱이다.

따라서 최대공약수가 1이라는 점을 이용해서 문제를 해결하였다.

 

import sys
import math

data = sys.stdin.readline
result = []
n = int(data()) #배열 원소 갯수
    
arr = map(int,data().split()) #배열

x = int(input())
for i in arr: #arr에 있는 원소들 중에
    if x != i and math.gcd(x,i) == 1: #x가 아니고 x와의 최대공약수가 1인 수
            result.append(i) #결과 리스트로
            
print(sum(result)/len(result)) #서로소들의 평균