Description

　　对于任何正整数x，其约数的个数记作g(x)。例如g(1)=1、g(6)=4。如果某个正整数x满足：g(x)>g(i) 0<i<x

，则称x为反质数。例如，整数1，2，4，6等都是反质数。现在给定一个数N，你能求出不超过N的最大的反质数么

？

Input

　　一个数N（1<=N<=2,000,000,000）。

Output

　　不超过N的最大的反质数。

Sample Input

1000

Sample Output

840

Solution

首先前12个质数之积是大于\(2e9\)的，那么显然反素数只会含有前12个质数。

然后爆搜就好了。

顺便说一句这个数列是可以在OEIS上找到的，编号为。

#include
    
     using namespace std;void read(int &x) {    x=0;int f=1;char ch=getchar();    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;}#define write(x) printf("%d\n",x)const int maxn = 1e7;const int n = 2e9;const int pri[] = {0,2,3,5,7,11,13,17,19,23,29,31,37,41};int top;struct data {    int s,d;    bool operator < (const data &r) const {return s
     
      12) {        if(r<=n) s[++top]=(data){r,d};          return ;    }    dfs(x+1,r,d);    for(int i=1;;i++) {        if(1ll*r*pri[x]>1ll*n) return ;        r*=pri[x];dfs(x+1,r,d*(i+1));    }    }int main() {    dfs(1,1,1);    sort(s+1,s+top+1);    int x;read(x);int rec=0,ans=0;    for(int i=1;i<=top;i++) {        if(s[i].d>rec) rec=s[i].d,ans=s[i].s;        if(s[i].s>x) return write(ans),0;    }write(ans);    return 0;}