首页 > 代码库 > hdu 1239

hdu 1239

2024-07-08 18:26:45   222人阅读

首先，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--){   //q30             for(int k=1;k<=i;k++){   //p31                 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

 


联系
我们