P4780 Phi的反函数 题解

bluewindde · 2024-09-24 21:11:09 · 题解

本题解是错解，详见 https://www.luogu.com.cn/discuss/988951

因为 \varphi(x) 的值只与 x 的不同质因子有关，又因为 2^{31} 之内的数的质因子个数不超过 10，所以容易枚举 10 个位置上填入的质因子打出朴素的暴力，简单剪枝后得到 20 分。

注意需要先判掉 x = n + 1 的情况。

考虑优化：因为 \varphi 的值只与质因子有关（而不是质因子幂次），所以不用重复填入质因子，得到 68 分。

此时 x 可以表示为不同质数的乘积，设为 x = p_1 p_2 p_3 \cdots p_m，则

即 \forall i \in [1, m]，有 (p_i - 1) \mid n，用这个剪枝即可。

剪枝后，搜索实际上是枚举选 / 不选质因子，时间复杂度 O(2^{\omega(n)} \sqrt n)。

实际实现中可以筛出一定范围内的质数，达到 O(2^{\omega(n)}) 的时间复杂度，本题筛到 2 \cdot 10^5 即可通过。

#include <iostream>

#define int long long

using namespace std;

const int lim = 2e5;
const int mxx = 1ll << 31;

bool vis[lim + 5];
int pr[lim + 5], tail;

int n;

static inline bool isprime(int x) {
    for (int i = 2; i * i <= x; ++i)
        if (x % i == 0)
            return false;
    return true;
}

int ans = mxx + 1;

static inline void dfs(int x, int ph, int las, int dep) {
    if (ph > n)
        return;
    if (x >= ans)
        return;
    if (ph == n)
        ans = x;
    if (n % ph)
        return;
    if (dep < 10)
        for (int i = 1; i < las; ++i)
            dfs(x * pr[i], ph * (pr[i] - 1), i, dep + 1);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    for (int i = 2; i <= lim; ++i) {
        if (!vis[i])
            pr[++tail] = i;
        for (int j = 1; j <= tail && i * pr[j] <= lim; ++j) {
            vis[i * pr[j]] = true;
            if (i % pr[j] == 0)
                break;
        }
    }
    cin >> n;
    if (n == 1) {
        cout << 1 << endl;
        return 0;
    }
    if (isprime(n + 1)) {
        cout << n + 1 << endl;
        return 0;
    }
    dfs(1, 1, tail, 1);
    if (ans > mxx)
        cout << -1 << endl;
    else
        cout << ans << endl;
    return 0;
}