题目描述
对于任何正整数x，其约数的个数记作g(x)。例如g(1)=1、g(6)=4。
如果某个正整数x满足：g(x)>g(i) 0<i<x，则称x为反质数。例如，整数1，2，4，6等都是反质数。
现在给定一个数N，你能求出不超过N的最大的反质数么？
输入输出格式
输入格式：
一个数N（1<=N<=2,000,000,000）。
输出格式：
不超过N的最大的反质数。
输入样例#1：
1000
输出样例#1：
840 这道题很明显要找到的是不大于n的约数数最多的数里面最小的
因为如果约数相同而另一个数比你小就不满足题意了
我们可以把一个数拆成一堆质因数的幂的和 S=2^x1+3^x2+...+p^xn(p仍旧为质数）
方案总数就是cnt=(x1+1)*(x2+1)*(x3+1)*…… 这个自己想想就知道了的
而我们只需要找前9个质数就好了因为前9个质数2*3*5*7*11*13*17*19*23*29=6,469,693,230>2,000,000,000
这样情况其实很少我们只需要来一次爆搜解决问题就好了哇
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;
int read(){
int ans=,f=,c=getchar();
while(c<''||c>''){if(c=='-') f=-; c=getchar();}
while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}
return ans*f;
}
int num[]={,,,,,,,,,,,,};
int n,ans,mx;
void dfs(LL now,LL sum,int step){
if(now>mx) mx=now,ans=sum;
if(now==mx&&ans>sum) ans=sum;
for(int i=;i<=;i++){
if(sum*num[step]>n) break;
sum=sum*num[step];
dfs(now*(i+),sum,step+);
}
}
int main()
{
n=read();
ans=;
dfs(,,);
printf("%d\n",ans);
return ;
}