前言
题目传送门 Luogu P1463 [POI 2001 R1 / ZJOI2006 / HAOI2007] 反素数
得到了 这篇题解 的启发，特此引流。
题目描述
对于任何正整数 \(x\)，其约数的个数记作 \(g(x)\)。例如 \(g(1)=1\)，\(g(6)=4\)。
如果某个正整数 \(x\) 满足：\(\forall 0 \lt i \lt x\)，都有 \(g(x) \gt g(i)\)，则称 \(x\) 为反素数。例如，\(1,2,4,6,12,24\) 等都是反素数。
现在给定一个正整数 \(N\)，你能求出不超过 \(N\) 的最大的反素数么？
题意
首先转换题意。由题意得，我们要求的这个反素数 \(x\) 应当满足以下两个性质：
性质（1）成立的原因如题。性质（2）成立的原因是，因为 \(x\) 是 \(\le n\) 的最大反素数，所以 \((x, n]\) 中的数不能是反素数。
于是我们知道，求最大的反素数，实际上是求 \((0,n]\) 范围内约数最多的数中的最小值。
思路
首先我们要知道给定范围内约数个数最多的数怎么求。
-
由唯一分解定理我们知道，任意一个大于二的正整数可被分解为若干素数的幂之积的形式；
-
又由约数个数定理我们知道，一个数的约数个数只与这些幂指数有关；
-
我们知道，在同样的范围内，作底数的质数越小，可能的指数就越大，从而约数就可能越多；
-
同时结合数据范围，我们知道最大的 \(n\) 也不可能有 \(>29\) 的质因子，因为最小的这几个素数之积超过了最大的 \(n\)；且这些质因子的指数最多是 \(30\) ，因为 \(2^{31}\) 超过了最大的 \(n\) 。
-
我们还可以通过推理得到，对我们所求的 \(x\) 按质因子从小到大进行分解，它们的指数一定是单调不增的。采取反证法，若 \(x\) 存在两个质因子 \(p_i>p_j\) ，且它们的指数 \(a_i>a_j\) ，我们就可以通过交换它们的指数得到一个更小的数，且由约数个数定理，这个更小的数约数个数不变。这与 \(x\) 是约数个数最多的数中的最小值矛盾。
所以我们打一个前 \(10\) 个素数的表，从最小的 \(2\) 开始逐个枚举每个质因数可能的指数，并保证指数递减。这个过程很适合爆搜。在搜索过程中，我们记录约数个数最多的数的最小值，即可得到答案。虽然数据很大，但是这个 dfs 跑得很快，原因是我们有几个优化，很好理解，不再赘述，详见代码。
代码
#include<iostream>
#define fastio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
#define MIKU 0
using namespace std;const int prime[15] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31}; //质数表int n, ans, maxc;int qpow(int a, int n) {int ans = 1;while(n > 0) {if(n & 1) ans *= a;a *= a;n >>= 1;}return ans;
}void dfs(int pid, int cnt, int s, int pw) {
//pid:当前要放的质因子的编号; cnt:当前约数个数; s:当前得数; pw:当前质因子的最大指数。if(s > n) return;if(cnt > maxc) ans = s, maxc = cnt;if(cnt == maxc) ans = min(ans, s); //更新答案，确保是最小值。for(int i=1; i<=pw; i++) {int tmp = qpow(prime[pid], i);if(s > n / tmp) break; //优化1：如果超过 n 就停止。除法防越界。dfs(pid+1, cnt*(i+1), s*tmp, i); //优化2：指数单调不增。}
}signed main() {fastio;cin>>n;dfs(1, 1, 1, 31); //最大指数是 31 。cout<<ans;return MIKU;
}