题目描述

对于任何正整数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的最大的反质数。

---

对于一个反质数n

 

一定有n=p1^(c1)+p2^(c2)+……+pm^(cm);

其中p1……pm为依次递增的质数

c1……cm为依次严格不上升的序列

 

根据范围可得p最多有10个不同的质数

 

暴力搜索就好

#include
      
       #define re return#define ll long long#define inc(i,l,r) for(int i=l;i<=r;++i) using namespace std;template
       
        inline void rd(T&x){    char c;bool f=0;    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;    x=c^48;    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);    if(f)x=-x;}ll n,m,ans,ans_cnt,a[20]={
    0,2,3,5,7,11,13,17,19,23,29};inline void dfs(ll x,ll up,ll y,ll cnt)//x：当前数，up :上界,y:第几层 {    if(cnt>ans_cnt||(cnt==ans_cnt&&x
        
         n)break;        dfs(now*x,i,y+1,cnt*(i+1));    }}int main(){    rd(n);    dfs(1,31,1,1);    printf("%lld",ans);    re 0;}