Project Euler 248

题目

Numbers for which Euler’s totient function equals $13!$

The first number n for which $\varphi(n)=13!$ is $6227180929$.

Find the $150,000^{\text{th}}$ such number.

解决方案

令$M=13!$。如果$\varphi(n)=M$，那么$n$的所有质因数$p$的欧拉函数$\varphi(p)=p-1$，都有$p-1|M$。

那么，先求出$M$的所有因数$d$，再将所有是质数的$d+1$存入数组$pr$中。

最终，$n$一定是由数组$pr$的一些质因子相乘而得。

考虑通过深度优先搜索，枚举出所有$\varphi(n)=M$的$n$值。从大到小枚举所有质因数并逐一尝试，这样做可以有效减少枚举量。

代码

from tools import fac, is_prime, divisors

N = 13
Q = 150000
M = fac(N)
pr = [x + 1 for x in divisors(M) if is_prime(x + 1)][::-1]
ls = []


def dfs(f, n, rest):
    if rest == 1:
        ls.append(n)
    for i in range(f, len(pr)):
        p = pr[i]
        if rest % (p - 1) == 0:
            dfs(i + 1, n * p, rest // (p - 1))
            t_n, t_rest = n * p, rest // (p - 1)
            while t_rest % p == 0:
                t_rest //= p
                t_n *= p
                dfs(i + 1, t_n, t_rest)


dfs(0, 1, M)
ls.sort()
ans = ls[Q - 1]
print(ans)
# 16s~17s