[HAOI2007] 反素数

题意

• 设 $g(x)$ 为 $x$ 的因数个数。
• 定义反素数为满足 $\forall 0 \lt y \lt x, g(y) < g(x)$ 的正整数。
• 求不大于 $n$ 的最大反素数

题解

首先设 $x$ 为反素数， $x = p_1^{k_1}p_2^{k_2} \ldots p_q^{k_q}, \ p_1 \lt p_2 \lt \ldots \lt p_q, 0 \le k_i$ 。

有 $k_1 \ge k_2 \ge \ldots \ge k_q$ 。

证明：若 $k_i \lt k_j, i \lt j$ ，则有 $y = \ldots p_i^{k_j} p_j^{k_i} \ldots$ ，使得 $g(y) = g(x), y < x$，显然不满足条件。

反素数为所有因数个数相同的数中最小的一个。

故暴力搜索所有质数，找出不大于 $n$ 的满足如上条件的因数个数最多的最小的数即可。

代码

提交记录

/*
author: byronwan
problem:
    url: https://www.luogu.com.cn/problem/P1463
    title: [HAOI2007] 反素数
date: 2022-09-11
*/

#include <bits/stdc++.h>

using namespace std;

const int primes[]
  = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 79, 83, 89, 97},
  p_cnt = 24;

int n;
int res_cnt, res_minx = 1e9;

void dfs(long long x, int cnt, int p, int lst_k)
{
    // cerr << "# " << cnt << " " << x << " " << p << " " << lst_k << endl;
    if (cnt > res_cnt || (cnt == res_cnt && x < res_minx)) res_cnt = cnt, res_minx = x;
    else if (cnt <= res_cnt && x >= res_minx) return;
    if (p >= p_cnt) return;

    long long acc = 1;
    int k = 0;
    while (x * acc <= n && k <= lst_k) {
        // cerr << "$ " << primes[p] << " " << k << endl;
        dfs(x * acc, cnt * (k + 1), p + 1, k);
        acc *= primes[p];
        k++;
    }
}

int main()
{
    cin >> n;
    dfs(1, 1, 0, 1e9);
    cout << res_minx << endl;
    cerr << res_cnt << endl;
}