首页 > 代码库 > 【noi 2.7_413】Calling Extraterrestrial Intelligence Again（算法效率）
【noi 2.7_413】Calling Extraterrestrial Intelligence Again（算法效率）
题意：给3个数M,A,B，求两个质数P,Q。使其满足P*Q<=M且A/B<=P/Q<=1，并使P*Q最大。输入若干行以0,0,0结尾。
解法：先线性筛出素数表，再枚举出P，二分出对应的最大的Q，得出最佳答案。
注意——二分时通过pri[]的下标尽量大来实现，比递归快了很多，具体请见代码。
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 using namespace std; 6 #define M 100010 7 #define D 1010 8 9 bool np[M/10];10 int pri[M/20];11 int cnt;12 13 int mmin(int x,int y) {return x<y?x:y;}14 void init_pri()15 {//116 cnt=0;17 memset(np,false,sizeof(np));18 for (int i=2;i<=M/10;i++)19 {20 if (!np[i]) pri[++cnt]=i;21 for (int j=1;j<=cnt&&i*pri[j]<=M/10;j++)22 {23 np[i*pri[j]]=true;24 if (i%pri[j]==0) break;//不能调到前一句前25 }26 }27 /*228 cnt=0;29 memset(np,false,sizeof(np));30 for (int i=2;i<=M/10;i++)31 {32 if (np[i]) continue;33 pri[++cnt]=i;34 for (int j=2;i*j<=M/10;j++)35 np[i*j]=true;36 }37 */38 }39 int main()40 {41 init_pri();42 while (1)43 {44 int m,x,y;45 scanf("%d%d%d",&m,&x,&y);46 if (m+x+y==0) break;47 int pp,qq; pp=qq=0;48 for (int i=1;i<=cnt;i++)49 {50 int p=pri[i],lim=mmin(y*p/x,m/p);51 int tmp=i;52 for (int j=12;j>=0;j--)53 if (tmp+(1<<j)<=cnt && pri[tmp+(1<<j)]<=lim) tmp+=(1<<j);54 if (tmp==i && p*pri[tmp]>m) break;55 int q=pri[tmp];56 if (p*q>pp*qq) pp=p,qq=q;57 }58 printf("%d %d\n",pp,qq);59 }60 return 0;61 }
而关于线性筛素数，我有2种方法。第一种是每得到一个素数，就让它乘1、2、3...，得到的数标记为不是素数；第二种是最常见的，也是比较快的，每个数都与已得到的素数相乘，得到的数也标记为不是素数，但要小心：当这个数是当前枚举的素数的倍数时，就要跳出循环了。而语句的顺序在理论上为什么在后面，我就不清楚了...O.O
我附上我的测试速度的代码吧,大家可以顺带学一下计时的方法~测出来方法一是0.02s，方法二是0.01s。
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<ctime> 5 #include<iostream> 6 using namespace std; 7 #define M (int)1e6 8 9 bool np[M];10 int pri[M];11 int cnt;12 13 int mmin(int x,int y) {return x<y?x:y;}14 void init_pri()15 {16 cnt=0;17 memset(np,false,sizeof(np));18 for (int i=2;i<=M;i++)19 {20 if (np[i]) continue;21 pri[++cnt]=i;22 for (int j=2;i*j<=M;j++)23 np[i*j]=true;24 }25 }26 int main()27 {28 init_pri();29 printf("Time used=%.2lf\n",(double)clock()/CLOCKS_PER_SEC);30 return 0;31 }
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<ctime> 5 #include<iostream> 6 using namespace std; 7 #define M (int)1e6 8 9 bool np[M];10 int pri[M];11 int cnt;12 13 int mmin(int x,int y) {return x<y?x:y;}14 void init_pri()15 {16 cnt=0;17 memset(np,false,sizeof(np));18 for (int i=2;i<=M;i++)19 {20 if (!np[i]) pri[++cnt]=i;21 for (int j=1;j<=cnt&&i*pri[j]<=M;j++)22 {23 np[i*pri[j]]=true;24 if (i%pri[j]==0) break;//hou25 }26 }27 }28 int main()29 {30 init_pri();31 printf("Time used=%.2lf\n",(double)clock()/CLOCKS_PER_SEC);32 return 0;33 }
【noi 2.7_413】Calling Extraterrestrial Intelligence Again（算法效率）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。