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

Problem link

boj 11689

Classification

Mathematics, Number theory, Eulerian functions

Description

Recently, I've been practicing solving Backzun problems without categorizing them in order to really improve my skills. However, when I come across something like this problem, I get quite a headache.

In the case of this problem, I initially thought that I should at least try to get it below O(N), since I need to be able to check the numbers up to 10¹² in 1 second. I thought that if it was a prime factorization, I could just do a normal prime factorization and not have any overlapping numbers, so I used the following code.

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)

However, the time complexity was not satisfactory based on this code, so I decided to check the tags and found a new friend in 오일러 피 함수.

As it turns out, the problem itself is a function called

φ(n) = {n, the number of natural numbers less than or equal to n that are prime to each other}

I was able to implement it like this

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. start at 2 and keep going.
2. if the number is divisible, divide it as much as it is divisible. (prime factorization)
3. subtract from the resulting number because multiples of that number cannot be prime.
4. If there is a number left at the end, subtract it from the resulting number because it is a prime number and multiples of that prime number cannot be prime.

This is where things got a little tricky.

result -= result // checker

I wondered why we were removing the divisor from result instead of removing number // checker, but it makes sense. If we remove the multiples of n, and then remove the same number of multiples of m, we end up with 2 multiples of n * m!

To handle these duplicates, we subtract the number of multiples of that number from the number that has already been subtracted once.

Anyway, once you understand how to solve it, it becomes a very easy problem. This seems to be the case with number theory problems, which is great for learning, but a little frustrating because the first approach is always hard...

Solution code

# 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))