COJN 0486 800401反质数呵呵呵呵呵

800401反质数

难度级别：A；运行时间限制：1000ms；运行空间限制：51200KB；代码长度限制：2000000B

试题描述

将正整数 x 的约数个数表示为 g(x)。例如，g(1)=1,g(4)=3, g(6)=4。

如果对于任意正整数y，当 0 < y < x 时，x 都满足 g(x) > g(y), 则称 x 为反质数。整数 1，2，4，6 等都是反质数。

现在任意给定两个正整数 M, N，其中，M < N <= 20000000，按从小到大输出其中（包括 M 和 N）的所有反质数。如果没有，则输出大写的NO。

输入

一行，包含两个正整数M和N，用单个空格隔开。

输出

在一行内输出所有反质数，以逗号间隔。如果没有，则输出 NO。

输入示例

1 13

输出示例

1,2,4,6,12

其他说明

题解：我非常想分享一下这道题的艰辛历程= =

首先：这还不好办？分块打表！结果发现它不是问数量。。。= =

那也可以呀？我们不分块直接打表不好嘛？

于是就有了下图，发现根本交不上去。。。= =

COJN 0486 800401反质数呵呵呵呵呵-LMLPHP

那那那。。。窝萌就把所有的反质数都打出来呗。。。。

结果。。。。。。。。。。。。。。。。。。。。。。

COJN 0486 800401反质数呵呵呵呵呵-LMLPHP

呵，呵，呵，呵，呵，呵，呵，呵，呵，呵，呵，呵，呵，呵，呵，呵，呵，呵，呵，呵，呵，呵，呵，呵，呵，呵，呵，呵，呵，呵，呵，呵，呵

这个惨痛的教训告诉窝萌：打表，是一项技术活。。。。。。。。。。。。。。。。

。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。

附打表程序：

 #include<iostream>

 #include<cstdio>

 #include<cmath>

 #include<algorithm>

 #include<queue>

 #include<cstring>

 #define PAU putchar(' ')

 #define ENT putchar('\n')

 using namespace std;

 const int maxn=+,maxv=;

 int a[maxn];bool b[maxn];

 int cal(int x){

     if(x==)return ;

     int lim=(int)sqrt(x),ans=;

     for(int i=;i<=lim;i++)if(x%i==)ans+=;

     if(lim*lim==x)ans-=;return ans;

 }

 inline int read(){

     int x=,sig=;char ch=getchar();

     for(;!isdigit(ch);ch=getchar())if(ch=='-')sig=;

     for(;isdigit(ch);ch=getchar())x=*x+ch-'';

     return sig?x:-x;

 }

 inline void write(int x){

     if(x==){putchar('');return;}if(x<)putchar('-'),x=-x;

     int len=,buf[];while(x)buf[len++]=x%,x/=;

     for(int i=len-;i>=;i--)putchar(buf[i]+'');return;

 }

 void init(){

     freopen("b.txt","w",stdout);

     for(int i=;i<=maxv;i++)a[i]=cal(i);int mx=;b[]=true;

     for(int i=;i<=maxv;i++)if(mx<a[i])mx=a[i],b[i]=true;

     int cnt=;

     for(int i=;i<=maxv;i++){

         if(b[i])a[cnt++]=i;

     }

     int tot=;

     for(int i=;i<cnt;i++){

         if(++tot==)tot=,ENT;

         printf("p[%d]=%d;",i,a[i]);

     }

     return;

 }

 void work(){

     return;

 }

 void print(){

     return;

 }

 int main(){init();work();print();return ;}

AC代码。。。

 #include<iostream>

 #include<cstdio>

 #include<cmath>

 #include<algorithm>

 #include<queue>

 #include<cstring>

 #define PAU putchar(' ')

 #define ENT putchar('\n')

 using namespace std;

 const int maxn=+;int p[maxn];

 inline int read(){

     int x=,sig=;char ch=getchar();

     for(;!isdigit(ch);ch=getchar())if(ch=='-')sig=;

     for(;isdigit(ch);ch=getchar())x=*x+ch-'';

     return sig?x:-x;

 }

 inline void write(int x){

     if(x==){putchar('');return;}if(x<)putchar('-'),x=-x;

     int len=,buf[];while(x)buf[len++]=x%,x/=;

     for(int i=len-;i>=;i--)putchar(buf[i]+'');return;

 }

 void init(){

     p[]=;p[]=;p[]=;p[]=;p[]=;p[]=;p[]=;p[]=;p[]=;

     p[]=;p[]=;p[]=;p[]=;p[]=;p[]=;p[]=;p[]=;p[]=;p[]=;

     p[]=;p[]=;p[]=;p[]=;p[]=;p[]=;p[]=;p[]=;p[]=;p[]=;

     p[]=;p[]=;p[]=;p[]=;p[]=;p[]=;p[]=;p[]=;p[]=;p[]=;

     p[]=;p[]=;p[]=;p[]=;p[]=;p[]=;p[]=;p[]=;p[]=;p[]=;

     p[]=;

     return;

 }

 void work(){

     int n=read(),m=read();bool flag=false;

     for(int i=;i<;i++){

         if(n<=p[i]&&p[i]<=m){

             if(flag)putchar(',');

             else flag=true;

             write(p[i]);

         }

     }

     if(!flag)puts("NO");

     return;

 }

 void print(){

     return;

 }

 int main(){init();work();print();return ;}

反质数

COJN 0486 800401反质数 呵呵呵呵呵

COJN 0486 800401反质数呵呵呵呵呵