[BOJ 11689, Python] GCD(n, k) = 1

문제 링크

BOJ 11689

분류

수학, 정수론, 오일러 피 함수

설명

최근 백준 문제를 풀이할 때 진짜 실력을 높이기 위해서는 문제 분류를 배제하고 풀이해야 한다고 생각하여 실천 중에 있다. 하지만 이번에 정리하는 이 문제와 같은 것들을 만나면 상당히 골치가 아파지게 된다.

이 문제의 경우, 처음에 1012 까지 숫자를 1초 안에 체크할 수 있어야 하기 때문에 최소한 O(N) 수준보다 아래로 끌어내려야 한다는 생각까진 했었다. 서로소 판정이라면 보통 소인수분해를 진행하고 겹치는 숫자가 없으면 될 것이라고 생각했기 때문에 이하의 코드를 활용했었다.

def factorize(target_number: int) -> list:

    result = []
    prime_list = find_prime(target_number)

    now_number = target_number
    while now_number > 1:
        for each_prime in prime_list:
            if each_prime > now_number:
                break

            elif not now_number % each_prime:
                while not now_number % each_prime:
                    now_number //= each_prime
                result.append(each_prime)

하지만 이러한 코드를 기반으로 한 경우 시간복잡도를 만족시킬 수 없었다. 결국 고민 끝에 태그를 확인하기로 결정했고, 오일러 피 함수 라는 새로운 친구를 만나게 되었다.

확인해보니 이 문제 그 자체인 함수였는데

φ(n) = {n 이하의 자연수 중 n과 서로소인 자연수의 갯수}

요렇게 구현할 수 있었다.

def euler_phi(number: int) -> int:
    '''
    오일러 피 함수를 활용한 자연수 n과 서로소인 수의 갯수를 구하는 함수
    '''

    checker = 2
    result = number

    while pow(checker, 2) <= number:
        if not number % checker:
            while not number % checker:
                number //= checker

            result -= result // checker

        checker += 1

    if number > 1:
        result -= result // number

    return result

1. 2부터 쭉 나아가면서 진행한다.
2. 나눠지는 수가 있다면 나눌 수 있을만큼 나눠준다. (소인수분해)
3. 해당 수의 배수는 서로소일 수 없으므로 결과 갯수에서 뺀다.
4. 마지막에 남은 수가 있다면 해당 수는 소수, 해당 소수의 배수도 서로소가 될 수 없으므로 결과 갯수에서 빼준다.

여기서 조금 어려운 부분이 이 부분이었다.

result -= result // checker

왜 number // checker 를 제거하는 게 아니라 result에서 나눈 값을 제거하는지가 궁금했는데 사실 당연한 부분이었다. n 의 배수를 없애주고 m 의 배수도 그 갯수 그대로 없애준다면 결과적으로 n * m 의 배수는 2번 빠지게 되는 것이다!

이러한 중복 처리되는 숫자를 처리하기 위해 이미 한 번 빠진 갯수에서 해당 숫자의 배수만큼을 빼게 되는 것라고 할 수 있겠다.

어찌되었건 해당 풀이법을 이해하는 순간 아주 쉬운 문제가 된다. 정수론 문제들이 이런 경향이 있는 거 같은데 배울 때는 좋지만 막상 첫 접근이 항상 어려워서 좀 불편하다..

풀이 코드

# GCD(n, k) = 1


def euler_phi(target_number: int):
    result = target_number
    check_number = 2

    while pow(check_number, 2) <= target_number:
        if not target_number % check_number:
            while not target_number % check_number:
                target_number //= check_number
            result -= result // check_number
        check_number += 1

    if target_number > 1:
        result -= result // target_number

    return result


target = int(input())
print(euler_phi(target))