题目描述

对于任何正整数 $x$，其约数的个数记作 $g(x)$。

如果某个正整数 $x$ 满足：对于任意的小于 $x$ 的正整数 $i$，都有 $g(x)>g(i)$，则称 $x$ 为反素数。
现在给定一个数 $N$，请求出不超过 $N$ 的最大的反素数。

输入样例:

1000

输出样例:

840

算法1

(DFS)

为了方便描述，定义如下表示方法:
对于任意正整数 $n$，第 $k$ 个质数在 $n$ 中有 $t$ 次，则在第 $k$ 位值位 $t$。
如 $6 = <1, 1, 0, 0……>$，$360 = <3, 2, 1, 0……>$
则令反素数 $n = <c_1, c_2, ……, c_m, 0, 0……>$
则 $c_1 ≥ c_2 ≥ c_3 ≥ …… ≥ c_m ≥ 0$
$DFS$ 即可

时间复杂度: $O(玄学)$

C++ 代码

#include <bits/stdc++.h>
using namespace std;

long long n;
long long prime[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 27, 29, 31};

long long max_num = -1, max_factor_num = -1;                               

void dfs(long long x, long long y, long long now_num, long long factor_num)
{
    if (now_num > n or x > 10)
        return ;

    if (factor_num > max_factor_num)
    {
        max_factor_num = factor_num;
        max_num = now_num;
    }
    else if (factor_num == max_factor_num)
            max_num = min(max_num, now_num);

    for (int i = 1; i <= y; i++)
    {
        now_num *= prime[x];
        if (now_num > n)
            return ;
        dfs(x + 1, i, now_num, factor_num * (i + 1));
    }
}

int main()
{
    cin >> n;

    dfs (0, 40, 1, 1);

    cout << max_num;
    return 0;
}