原题面：https://www.acwing.com/problem/content/200/
题目大意：对于任何正整数x，其约数的个数记作g(x)，例如g(1)=1、g(6)=4。如果某个正整数x满足：对于任意的小于x的正整数 i，都有g(x)>g(i) ，则称x为反素数。例如，整数1，2，4，6等都是反素数。现在给定一个数N，请求出不超过N的最大的反素数。
输入描述：一个正整数N。
输出描述：一个整数，表示不超过N的最大反素数。
输入样例：
1000
输出样例：
840
分析：引理1：1~N中最大的反质数，就是1~N中约数个数最多的数中最小的一个。引理2：1~N中任何数的不同质因子都不会超过10个，且所有质因子的指数总和不会超过30。
代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll v[10]={2,3,5,7,11,13,17,19,23,29},n,ans; ll maxnum; ll spow(ll a,ll b){ ll res=1; while(b){ if(b&1) res*=a; a*=a; b>>=1; } return res; } void dfs(ll tol,int num,int p,ll now) { if (p == 10) { if(( tol == maxnum && now < ans )|| tol > maxnum ){ ans = now; maxnum = tol; } return; } for (int i = 0; i <= num; i++) { ll temp = now * spow(v[p], i); if (temp > n) return; dfs(tol * (i + 1), i, p + 1, temp); } } int main(){ maxnum = 0; ans = 0; scanf("%lld", &n); dfs(1, 32, 0, 1); printf("%lld\n",ans); return 0; }
原文：https://www.cnblogs.com/SwiftAC/p/12110795.html