【反素数】

题目

思路

• 首先分析  的性质
  • 一定是  中约数最大的
  • 一定是约数同是最大的数字中值中最小的
• 进一步挖掘性质，紧贴枚举的做法
  • 约数最大值最小（也决定了层数、其它约束），是枚举的比较条件
  • 实现上述目的，枚举的质数种类在大小上是连续的，指数是不严格单调递减的（分支方式）
• 分析采取的方案
  • 通过 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;
}