luogu P1463 & AcWing 198 反素数 题解

题目传送门

• \(\text{luogu}\)
• \(\text{AcWing}\)

题意简述

给定 \(n\) ，求小于等于 \(n\) 的最大反素数。
反素数 \(n\) 定义：任意的 \(x\) 满足 \(x\le n\)，则 \(x\) 的因数个数小于 \(n\) 的因数个数。

\(\texttt{SOLUTION}\)

容易发现反素数的两个性质：

• 质因数个数尽可能的多。（然鹅由于 \(n\le10^9\)，所以质因数个数\(\le 9\)，且质因子次数 \(\le30\)）。
• 质因子越大，次数越低。（显然）

然后爆搜即可。

\(\texttt{AC CODE}\)

咕咕咕