hdu1239 参考答案

   1 /*
   2 hdu 1239 简单搜索＋剪枝
   3 ymc 2008/09/18
   4 题目大意：
   5 给定1<=m<=10000,1<=a<=b<=1000,求两个质数p,q
   6 满足：p<=q,使得a/b<=p/q<=1,pq<=m，并且pq值最大。
   7 分析鱼解题思路：
   8 由pq<=m,得到p/q<=m/(q*q),结合a/b<=p/q<=1
   9 得到q*q<=m*b/a,在有m，a，b的取值范围得到
  10 q<=10000;同时2<=p<=q。
  11 先求出10000以内的所有质数，然后对q，p从大到小搜索。
  12 注意剪枝。
  13 */
  14 
  15 #include <iostream>
  16 using namespace std;
  17 const int N=10000;
  18 bool flag[N];
  19 int prim[N]={2};
  20 int num=1;
  21 int m,a,b;
  22 void Init()//用伊拉脱森（Eratosthens）筛求质数
  23 {
  24     memset(flag,1,sizeof(flag));
  25     flag[0]=flag[1]=false;
  26     for(int i=0;i<N;i=i+2)
  27         flag[i]=false;
  28     int x;
  29     while(1)
  30     {
  31         x=prim[num-1]+1;
  32         while(flag[x]==false&&x<N)
  33             x++;
  34         if(x==N)
  35             break;
  36         prim[num++]=x;
  37         for(int i=x+x;i<N;i=i+x)
  38             flag[i]=false;
  39     }
  40 }
  41 void Search()
  42 {
  43     int Max=1;
  44     int p,q,p1,q1;
  45     int tmp;
  46     for(int i=num-1;i>=0;i--)
  47     {
  48         q=prim[i];
  49         if(q+q>m)//剪枝，p>=2
  50             continue;
  51         if(q*q<Max)//剪枝,p<=q
  52             break;
  53         for(int j=i;j>=0;j--)
  54         {
  55             p=prim[j];
  56             tmp=p*q;
  57             if(tmp>m)//剪枝
  58                 continue;
  59             if(tmp<=Max)//剪枝
  60                 break;
  61             if(a*q<=b*p&&tmp>Max)
  62             {
  63                 Max=tmp;
  64                 p1=p;
  65                 q1=q;
  66             }
  67         }
  68     }
  69     printf("%d %d\n",p1,q1);
  70 }
  71 int main()
  72 {
  73     Init();
  74     while(scanf("%d %d %d",&m,&a,&b))
  75     {
  76         if(m==0&&a==0&&b==0)
  77             break;
  78         Search();
  79     }
  80 }