HYSBZ 1053 反质数

input

n 1<=n<=2000000000

output

不大于n的最大反质数

对于任何正整数x，其约数的个数记作g(x)。例如g(1)=1、g(6)=4。
如果某个正整数x满足：g(x)>g(i) 0<i<x，则称x为反质数。例如，整数1，2，4，6等都是反质数。

做法：直接打表查找

 #include <cstdio>

 #include <queue>

 #include <cstring>

 #include <iostream>

 #include <cstdlib>

 #include <algorithm>

 #include <vector>

 #include <map>

 #include <set>

 #include <ctime>

 #include <cmath>

 #include <cctype>

 #define MAX 100000

 #define INF 2000000000

 #define LL long long

 int cas=,T,n,a[MAX],an,p[]={,,,,,,,,,};

 struct node

 {

     int b[],n,v,g;            //b数组是质数对应的次方,v是值,g是约数个数,n是质因子个数

     bool operator<(node a)const { return v>a.v; }

 };

 void init()

 {

     std::priority_queue<node>q;

     a[]=;an=;

     int ming=;//当前最大的约数个数

     node u;

     u.v=;u.n=;u.b[]=;u.g=;

     q.push(u);

     while(!q.empty())

     {

         u=q.top();q.pop();

 //        printf("%d %d %d\n",u.v,u.g,u.n);

         if(u.g>ming) { ming=u.g;a[an++]=u.v; }//比当前最大约数个数大的统计

         else continue;

         for(int i=;i<=u.n;i++)//出队后将每个质数对应的次方加一放进队列里

         {

             node v;

             memcpy(&v,&u,sizeof(node));

             LL tmp=(LL)v.v*p[i];

             v.b[i]++;

             v.g=v.g/v.b[i]*(v.b[i]+);

             if(tmp<=INF) v.v=tmp;

             if(tmp<=INF&&v.g>ming) q.push(v);

 //            printf("aaa:%d %d %d\n",v.v,v.g,v.n);

         }

         if(u.n+<)//增加一个质因子

         {

             node v;

             memcpy(&v,&u,sizeof(node));

             v.n++;v.b[v.n]=;v.g*=;

             LL tmp=(LL)v.v*p[v.n];

             if(tmp<=INF) v.v=tmp;

             if(tmp<=INF&&v.g>ming) q.push(v);

         }

     }

     a[an++]=INF+;

     printf("%d\n",an);

     for(int i=;i<an;i++) printf("%d,",a[i]);

 }

 int main()

 {

     //freopen("in","r",stdin);

     //scanf("%d",&T);

     init();

     while(scanf("%d",&n)==) printf("%d\n",*(std::upper_bound(a,a+an,n)-));

     //printf("time=%.3lf",(double)clock()/CLOCKS_PER_SEC);

     return ;

 }