hdu 1239

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

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

 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
",p,q);
39     }
40     return 0;
41 }

View Code