题目
思路
- 首先分析
的性质 - 一定是
![x \in [1,N]](https://latex.csdn.net/eq?x%20%5Cin%20%5B1%2CN%5D)
中约数最大的 - 一定是约数同是最大的数字中值中最小的
- 进一步挖掘性质，紧贴枚举的做法
- 约数最大值最小（也决定了层数、其它约束），是枚举的比较条件
- 实现上述目的，枚举的质数种类在大小上是连续的，指数是不严格单调递减的（分支方式）
- 分析采取的方案
- 通过 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;
}
