<—点个赞吧QwQ

宣传一下算法提高课整理{:target=”_blank”}

对于任何正整数 $x$，其约数的个数记作 $g(x)$，例如 $g(1)=1、g(6)=4$。

如果某个正整数 $x$ 满足：对于任意的小于 $x$ 的正整数 $i$，都有 $g(x)>g(i)$，则称 $x$ 为反素数。

例如，整数 $1，2，4，6$ 等都是反素数。

现在给定一个数 $N$，请求出不超过 $N$ 的最大的反素数。

输入格式

一个正整数 $N$。

输出格式

一个整数，表示不超过 $N$ 的最大反素数。

数据范围

$1 \\le N \\le 2\*10^9$

输入样例：

1000

输出样例：

840

思路

假设$[1,n]$中约数个数最多的数的约数个数为$s$。
则对于$[1,n]$中所有数，满足约数个数是$s$的所有数当中，反素数是这些数中最小的那个。
反证法：假设存在约数个数为$s$的两个数$a,b$，且$a > b$，则$g(a)\le g(b)$，但$a>b$，矛盾。因此反素数必定是这些数中最小的那个。

得到上属性之后，继续分析：

1. 对于数据范围$[1,2 \times 10^9]$，因为$2 \times3 \times5 \times7 \times9 \times11 \times13 \times17 \times19 \times23 \times29 > 2\times 10^9$，所以满足不同银子相乘的最大质数为$23$
2. 对数范围$[1,2 \times 10 ^ 9]$，因为$2{31}>2\times 10 ^ 9$，所以能够满足质因子的最大次数为$30$
3. 对于数据范围$[1,2\times10^9]$，质因子从小到大，其次数必定是不单调上升的。
   反证法：假设存在两个质因子$a,b$，且满足$a > b$，$a,b$的次数分别记作$k_a,k_b$，且$k_a>k_b$
   则对于反素数$x=\cdots a ^ {k_a}\cdot b^{k_b}\cdots$，必然存在数$x^\prime < x$
   而根据我们推到的第一个性质，$x^\prime$更有可能是所求的反素数，而并非$x$，故矛盾。

接下来，我们整理下我们的条件：

1. 质因子数量不单调递增
2. 质因子最大枚举到$23$
3. 单个质因子次数最多为$30$

代码

#include <iostream>
using namespace std;
typedef long long LL;
int n;
int primes[] = {2,3,5,7,11,13,17,19,23};
int ans,maxd;
void dfs (int u,int last,int num,int sum) {
    if (sum > maxd || (sum == maxd && num < ans)) maxd = sum,ans = num;
    if (u == 9) return ;
    for (int i = 1;i <= last;i++) {
        if ((LL)num * primes[u] > n) return ;
        num *= primes[u];
        dfs (u + 1,i,num,sum * (i + 1));
    }
}
int main () {
    cin >> n;
    dfs (0,30,1,1);
    cout << ans << endl;
    return 0;
}