首页 > 其他 > 详细

hdu 1239

时间:2014-06-21 06:52:12      阅读:369      评论:0      收藏:0      [点我收藏+]

首先,p,q>=2,所以p,q<=50000;

然后,我们观察a<=b<1000,而p,q<=100000。那么,q>=10000时,p<=10,则a/b<=1/1000,这已是下限,所以,我们认为p,q<=10000;

bubuko.com,布布扣
 1 #include <iostream>
 2 #include <cstdio>
 3 
 4 using namespace std;
 5 
 6 bool num[10005];
 7 int m,a,b;
 8 int pnum[10000]; int n;
 9 void type_table(){
10     num[1]=true;
11     for(int i=1;i<=10000;i++){
12         if(!num[i]){
13             pnum[++n]=i;
14             for(int k=i+1;k<=10000;k++){
15                 if(num[k]) continue;
16                 else if(k%i==0) num[k]=true;
17             }
18         }
19     }
20 }
21 
22 int main(){
23     n=0;
24     memset(num,false,sizeof(num));
25     type_table();
26     while(scanf("%d%d%d",&m,&a,&b)!=EOF){
27         if(m==0&&a==0&&b==0) break;
28         int p=0,q=0; int ans=0;
29         for(int i=n;i>=1;i--){   //q
30             for(int k=1;k<=i;k++){   //p
31                 if(a*pnum[i]<=b*pnum[k]&&pnum[i]*pnum[k]<=m&&pnum[i]*pnum[k]>ans){
32                     ans=pnum[i]*pnum[k];
33                     p=pnum[k];q=pnum[i];
34                 }
35                 else if(pnum[i]*pnum[k]>m) break;
36             }
37         }
38         printf("%d %d\n",p,q);
39     }
40     return 0;
41 }
View Code

 

hdu 1239,布布扣,bubuko.com

hdu 1239

原文:http://www.cnblogs.com/jie-dcai/p/3795353.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!