Luogu P1463 [POI 2001 R1 / ZJOI2006 / HAOI2007] 反素数 题解

前言

标题传送门 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\) 应当满意以下两个性子：

\[\begin{align}\forall 0 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 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