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

问题链接

boj 11689

分类

数学, 数论, 欧拉函数

描述

最近，我一直在练习解决不分类的 Backzun 问题，以提高我的实际能力。然而，当我遇到像这样的问题时，就变得相当头疼。

就这个问题而言，我起初认为至少应该尝试将其求解到 O(N) 以下，因为我需要在 1 秒钟内检查 10¹² 以下的数字。我使用了下面的代码，因为我认为如果是质因数分解，而且没有重叠的数字，就不会有问题。

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. 如果最后还剩下一个数，就从结果数中减去它，因为它是一个质数，而这个质数的倍数不能是质数。

这就是有点棘手的地方。

结果 -= 结果 // 校验

我曾想过为什么我们要从结果中移除除数，而不是移除 number // checker，但这是有道理的。如果我们去掉 n 的倍数，然后再去掉相同数目的 m 的倍数，最后就会得到两个 n * m 的倍数！

为了处理这些重复的数字，我们要从已经删除过一次的数字中减去该数字的倍数。

总之，一旦你明白了解决方法，这个问题就变得非常简单了。数论问题似乎都是这样，这对学习很有帮助，但有点令人沮丧，因为第一种方法总是很难

解题代码

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