백준 문제 풀이 - 서로소 평균 21920번

📜 문제 이해하기

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

💡 문제 재정의

각 수열에서 X와 서로소인 수들의 평균을 구하자.

✏️ 계획 수립

서로소란 두 수의 약수가 1밖에 없는 숫자들을 말한다.
이 문제는 서로소를 빠르게 구하는게 목표인 문제이기에 2부터 각 숫자까지 하나하나 비교하면 시간 초과가 발생한다. 즉, 서로소의 특성을 이용하여 문제를 풀어야 한다.
서로소는 다음과 같은 특징이 존재한다.

1) 두 수의 최대공약수가 1
2) 두 수의 최소공배수가 ab

둘중 어떤 방법을 써도 상관없지만 1번 방법을 채택했다.

💻 계획 수행

import sys


def get_gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a


if __name__ == '__main__':
    N = int(input())
    A = list(map(int, sys.stdin.readline().split()))
    X = int(input())

    disjoint = []
    for a in A:
        if get_gcd(a, X) == 1:
            disjoint.append(a)
    print(sum(disjoint) / len(disjoint))

🤔 회고

정수론과 관련된 파트이기에 서로소에 대한 이해와 유클리드 알고리즘을 사용할 줄 알아야 풀 수 있는 문제였다.