原题面: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的最大反素数。
输入样例:
输出样例:
分析:引理1:1~N中最大的反质数,就是1~N中约数个数最多的数中最小的一个。引理2:1~N中任何数的不同质因子都不会超过10个,且所有质因子的指数总和不会超过30。
代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll v[]={,,,,,,,,,},n,ans;
ll maxnum;
ll spow(ll a,ll b){
ll res=;
while(b){
if(b&)
res*=a;
a*=a;
b>>=;
}
return res;
}
void dfs(ll tol,int num,int p,ll now) {
if (p == ) {
if(( tol == maxnum && now < ans )|| tol > maxnum ){
ans = now;
maxnum = tol;
}
return;
}
for (int i = ; i <= num; i++) {
ll temp = now * spow(v[p], i);
if (temp > n) return;
dfs(tol * (i + ), i, p + , temp);
}
}
int main(){
maxnum = ;
ans = ;
scanf("%lld", &n);
dfs(, , , );
printf("%lld\n",ans);
return ;
}