[P4780] Phi の 反函数

· · 题解

本题解分为三个部分：

1. 欧拉函数定理

欧拉函数表示的是小于等于 n 的与 n 互质的数的个数，写作 \varphi(n) 。

1.1 \varphi(n) = \prod_{p | n}^{n} \frac{p - 1}{p}

1.2 欧拉函数是一个积性函数，即：对任意互质的正整数 n, m，有 \varphi(nm) = \varphi(n) \times \varphi(m)

1.3 质数 p 的欧拉函数等于 p - 1 。

2. 本题思路

本题求解反欧拉函数，即：已知与小于等于 x 且 x 互质的数有 n 个，求 x 的最小值。

有性质 1.1 可知，一个数质因子出现的次数多少对他的欧拉函数没有影响，由于要求 x 的最小值，所以当我们把所有质因子的指数均取 1 时，就会达到最小值。

所以可以将 x 表示为 p_1 \cdot p_2 \dots p_m ，将 n 表示为 (p_1 - 1)(p_2 - 1)\dots(p_m - 1)。

所以，我们可以将 n 分解为一些质数 -1（一定别忘了减一！！）的乘积，这可以用 dfs 来实现。

同时要保证分解的质数并不重复，这可以用一个 Map（或者数组）来记录该质数是否被搜索过。

3. 代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <unordered_map> // 用来记录当前数是否用过

using namespace std;

int n;
int res = 2147483647;
unordered_map<int, bool> Map;

bool is_prime(int n)
{
    if (n <= 1) return false;
    for (int i = 2; i <= n / i; i ++ )
        if (n % i == 0)
            return false;

    return true;
}

void dfs(int u, int arcphi, int rest)
{
    if (arcphi >= res) return; // 剪枝优化

    if (rest == 1) {
        res = min(res, arcphi);
        return;
    }

    if (is_prime(rest + 1)) dfs(u + 1, arcphi * (rest + 1), 1);
    // 如果当前剩余的数是一个大素数，那么我们就可以直接判掉
    for (int i = 2; i <= rest / i; i ++ )
        if (is_prime(i + 1) && rest % i == 0 && Map[i] == false)
        {
            Map[i] = true; // 记录一下已经被用过了
            dfs(i, arcphi * (i + 1), rest / i);
            Map[i] = false;
        }
}

int main()
{
    cin >> n;

    dfs(1, 1, n);

    cout << (res == 2147483647 ? -1 : res) << endl;

    return 0;
}