原题点这
前置知识点：反素数
反素数：
若 N \(\le\) \(2^{31}\)
-
1 ~ N 中的反素数，就是 1 ~ N中约数个数最多的数中 最小 的一个。
-
1 ~ N 中任何数的不同质因子都不会超过 10 个且所有质因子的质数都不会超过30。
-
x\(\in\)[1, N]，x 为反素数的必要条件是：x 分解质因数后可以写成
\(2^{c_1} + 3^{c_2} + 5^{c_3} + 7^{c_4} + 11^{c_5} + 13^{c_6} + 17^{c_7} + 19^{c_8} + 23^{c_9} + 29^{c_{10}}\)，
且 \({c_1} \ge {c_2} \ge {c_3} \ge {c_4} \ge {c_5} \ge {c_6} \ge {c_7} \ge {c_8} \ge {c_9} \ge {c_{10}}\)，
换句话说， x的质因子是连续的若干个最小的质数，并指数单调递减。
求法：
根据上面的三个引理，我们可以直接DFS，一次确认前 x个质数的指数，并满足指数单调递减，总成绩不超过N ，同时记录约数的个 数即可。最后利用 引理1 找到约数个数最多的数里最小的那个数即可。
我们可以把当前走到每一个素数前面的时候列举成一棵树的根节点，然后一层层的去找。找到什么时候停止呢？
1. 当前走到的数字已经大于我们想要的数字了
2. 当前枚举的因子已经用不到了
3. 当前因子大于我们想要的因子了
4. 当前因子正好是我们想要的因子（此时判断是否需要更新最小 ans ）
然后 dfs 里面不断一层一层枚举次数继续往下迭代
题意：
给你 一个正整数 n, 让你求一个拥有 n 个因子的最小正整数
思路：
即求因子数一定的最小反素数
AC代码：
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(0);
#define LL long long
#define ULL unsigned long long
#define INF ~0ULL
ULL p[16] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};
ULL n,ans;
// 枚举到的素数，当前因子的数量，当前因子总数，上一个素数的幂
void dfs(ULL depth, ULL temp, ULL num, ULL up)
{
if(num > n || depth >= 16) return;
if(num == n && ans > temp)
{
ans = temp; return;
}
for (ULL i = 1; i <= up; i ++ )
{
if(temp / p[depth] > ans) break;
dfs(depth + 1, temp *= p[depth], num * (i + 1), i);
}
}
void solve()
{
cin >> n;
ans = INF;
dfs(0, 1, 1, 64);
cout << ans << endl;
}
int main()
{
IOS
int T = 1;
//cin >> T;
while(T --)
{
solve();
}
return 0;
}