题目
思路
- 首先分析 的性质
- 一定是 中约数最大的
- 一定是约数同是最大的数字中值中最小的
- 进一步挖掘性质,紧贴枚举的做法
- 约数最大值最小(也决定了层数、其它约束),是枚举的比较条件
- 实现上述目的,枚举的质数种类在大小上是连续的,指数是不严格单调递减的(分支方式)
- 分析采取的方案
- 通过 dfs 枚举质因子数目来枚举不同的
- 用约数公式判断约数个数进行比较
- 准备枚举(深搜)
- 比较条件:约数最大值最小
- 深搜的层数:枚举到 9 种质数就结束
- 分支方式:当前质因子不同的指数
- 其它约束:值不超过
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;int n;
int p[9] = {2,3,5,7,11,13,17,19,23};
int min_num = INT_MAX, max_s;
void dfs(int u, int last, int num, int s)
{if(s > max_s || s == max_s && num < min_num){max_s = s;min_num = num;}if(u >= 9) return;LL mi = 1;for(int i = 1; i <= last; i++){mi *= p[u];if(num * mi > n) break;dfs(u+1, i, num * mi, s * (i+1));}
}
int main()
{cin >> n;dfs(0, 30, 1, 1);cout << min_num;return 0;
}