P1463 [POI2001] [HAOI2007] 反素数题解

可以发现，最大的不超过 \(n\) 的反素数就是 \(1\sim n\) 中因数最多的数字。

证明：

设 \(x, x\in[1, n]\) 为 \(1\sim n\) 中因数最多的数字，则 \(x<y \le n\) 都不会成为答案，因为存在 \(x < y\) 因数比 \(y\) 多，同时也不会存在 \(y' < x\) 的 \(y'\) 的因数比 \(x\) 多，因为定义，所以 \(x\) 即为不超过 \(n\) 的最大反素数。

然后可以爆搜质因数的指数，加一些剪枝可以很快搜出来（\(30ms\)）。

// Problem: P1463 [POI2001] [HAOI2007] 反素数
// Contest: Luogu
// Author: Moyou
// Copyright (c) 2023 Moyou All rights reserved.
// Date: 2023-09-02 14:05:50

#include <iostream>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
typedef long long ll;
int prime[] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29}, n; // 最多到23，因为它们乘起来已经超过2e9了
PII ans;
void dfs(int u, int now, int cnt, int lim) { // 顺序剪枝
    if(u > 10 || now > n) return ; // 可行性剪枝
    if(cnt > ans.y || (cnt == ans.y && now < ans.x)) ans = {now, cnt};
    for(int i = 1; i <= lim; i ++) {
        if(1ll * now * prime[u] > n) return ;
        now *= prime[u];
        dfs(u + 1, now, cnt * (i + 1), i);
    }
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    ans = {1, 1};
    dfs(1, 1, 1, 1e9);
    cout << ans.x << '\n';

    return 0;
}