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

問題リンク

BOJ 11689

分類

数学、整数論、オイラー・ピー関数

説明

最近、Baekjoonの問題を解く際、真の実力を高めるためには問題の分類を気にせず解くべきだと考え、実践している。しかし、今回取り上げるこの問題のようなものに出くわすと、かなり頭を悩ませることになる。

この問題の場合、最初に¹0¹²までの数字を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))