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

其他说明

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

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

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

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

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

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

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

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

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

附打表程序：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<algorithm>
 5 #include<queue>
 6 #include<cstring>
 7 #define PAU putchar(' ')
 8 #define ENT putchar('
')
 9 using namespace std;
10 const int maxn=20000000+10,maxv=20000000;
11 int a[maxn];bool b[maxn];
12 int cal(int x){
13     if(x==1)return 1;
14     int lim=(int)sqrt(x),ans=2;
15     for(int i=2;i<=lim;i++)if(x%i==0)ans+=2;
16     if(lim*lim==x)ans-=1;return ans;
17 }
18 inline int read(){
19     int x=0,sig=1;char ch=getchar();
20     for(;!isdigit(ch);ch=getchar())if(ch=='-')sig=0;
21     for(;isdigit(ch);ch=getchar())x=10*x+ch-'0';
22     return sig?x:-x;
23 }
24 inline void write(int x){
25     if(x==0){putchar('0');return;}if(x<0)putchar('-'),x=-x;
26     int len=0,buf[15];while(x)buf[len++]=x%10,x/=10;
27     for(int i=len-1;i>=0;i--)putchar(buf[i]+'0');return;
28 }
29 void init(){
30     freopen("b.txt","w",stdout);
31     for(int i=1;i<=maxv;i++)a[i]=cal(i);int mx=1;b[1]=true;
32     for(int i=2;i<=maxv;i++)if(mx<a[i])mx=a[i],b[i]=true;
33     int cnt=0;
34     for(int i=1;i<=maxv;i++){
35         if(b[i])a[cnt++]=i;
36     }
37     int tot=0;
38     for(int i=0;i<cnt;i++){
39         if(++tot==10)tot=0,ENT;
40         printf("p[%d]=%d;",i,a[i]);
41     }
42     return;
43 }
44 void work(){
45     return;
46 }
47 void print(){
48     return;
49 }
50 int main(){init();work();print();return 0;}

AC代码。。。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<algorithm>
 5 #include<queue>
 6 #include<cstring>
 7 #define PAU putchar(' ')
 8 #define ENT putchar('
')
 9 using namespace std;
10 const int maxn=50+10;int p[maxn];
11 inline int read(){
12     int x=0,sig=1;char ch=getchar();
13     for(;!isdigit(ch);ch=getchar())if(ch=='-')sig=0;
14     for(;isdigit(ch);ch=getchar())x=10*x+ch-'0';
15     return sig?x:-x;
16 }
17 inline void write(int x){
18     if(x==0){putchar('0');return;}if(x<0)putchar('-'),x=-x;
19     int len=0,buf[15];while(x)buf[len++]=x%10,x/=10;
20     for(int i=len-1;i>=0;i--)putchar(buf[i]+'0');return;
21 }
22 void init(){
23     p[0]=1;p[1]=2;p[2]=4;p[3]=6;p[4]=12;p[5]=24;p[6]=36;p[7]=48;p[8]=60;
24     p[9]=120;p[10]=180;p[11]=240;p[12]=360;p[13]=720;p[14]=840;p[15]=1260;p[16]=1680;p[17]=2520;p[18]=5040;
25     p[19]=7560;p[20]=10080;p[21]=15120;p[22]=20160;p[23]=25200;p[24]=27720;p[25]=45360;p[26]=50400;p[27]=55440;p[28]=83160;
26     p[29]=110880;p[30]=166320;p[31]=221760;p[32]=277200;p[33]=332640;p[34]=498960;p[35]=554400;p[36]=665280;p[37]=720720;p[38]=1081080;
27     p[39]=1441440;p[40]=2162160;p[41]=2882880;p[42]=3603600;p[43]=4324320;p[44]=6486480;p[45]=7207200;p[46]=8648640;p[47]=10810800;p[48]=14414400;
28     p[49]=17297280;
29     return;
30 }
31 void work(){
32     int n=read(),m=read();bool flag=false;
33     for(int i=0;i<50;i++){
34         if(n<=p[i]&&p[i]<=m){
35             if(flag)putchar(',');
36             else flag=true;
37             write(p[i]);
38         }
39     }
40     if(!flag)puts("NO");
41     return;
42 }
43 void print(){
44     return;
45 }
46 int main(){init();work();print();return 0;}

COJN 0486 800401反质数 呵呵呵呵呵

COJN 0486 800401反质数呵呵呵呵呵