| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 9219 | Accepted: 3669 |
Description
to a rectangular picture with 23 x 73 pixels. Since both 23 and 73 are prime numbers, 23 x 73 is the unique possible size of the translated rectangular picture each edge of which is longer than 1 pixel. Of course, there was no guarantee that the receivers
would try to translate the message to a rectangular picture. Even if they would, they might put the pixels into the rectangle incorrectly. The senders of the Arecibo message were optimistic.
We are planning a similar project. Your task in the project is to find the most suitable width and height of the translated rectangular picture. The term "most suitable" is defined as follows. An integer m greater than 4 is given. A positive fraction a/b less
than or equal to 1 is also given. The area of the picture should not be greater than m. Both of the width and the height of the translated picture should be prime numbers. The ratio of the width to the height should not be less than a/b nor greater than 1.
You should maximize the area of the picture under these constraints.
In other words, you will receive an integer m and a fraction a/b. It holds that m > 4 and 0 < a/b <= 1. You should find the pair of prime numbers p, q such that pq <= m and a/b <= p/q <= 1, and furthermore, the product pq takes the maximum value among such
pairs of two prime numbers. You should report p and q as the "most suitable" width and height of the translated picture.
Input
of the input and should not be treated as data to be processed.
The integers of each input triplet are the integer m, the numerator a, and the denominator b described above, in this order. You may assume 4 < m <= 100000 and 1 <= a <= b <= 1000.
Output
Each output line contains a single pair. A space character is put between the integers as a delimiter. No other characters should appear in the output.
Sample Input
5 1 2 99999 999 999 1680 5 16 1970 1 1 2002 4 11 0 0 0
Sample Output
2 2 313 313 23 73 43 43 37 53
Source
这个题，题目很长，但是要描述的问题却很简单：
他是说：给你三个数：m,a,b
现在我们需要计算出两个质数:p和q，而且他们满足这两个条件：
p*q<=m和a/b<=p/q<=1
现在需要计算出p和q而且让p*q尽量大
比如说
1680 5 16
我们可以计算出p=23 q=73时
p*q最大，而且p*q<=m，a/b<=p/q<=1
思路：首先可以通过质数打表，打出一张范围为10000以内的质数表
然后需要明确的是：直接暴力枚举肯定是不行的、所以需要剪枝，我是这样优化算法的：
我们可以注意到在某一个m值得情况下，有一些小于m的值的质数根本不可能去到
还是以m=1680 a=5 b=16来举例，假设当前枚举的质数为x
那么既然选了这个x必然另外一个质数不可能小于x*5/16所以就可以得到一个方程
5/16*x^2<=1680
这样可以解出x=73.....（取整）
于是乎，在这个例子中任何大于73的数据都是不可取的，所以首先就可以确定枚举范围，这样可以让枚举量大大减少。。
于是首先计算范围，计算出范围之后在进行枚举和比较，于是就可以得到最后的最优解
我的代码是这样的：
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
struct node
{
bool flag;
int num;
};
node loop[10005];
int prime[10005];
int number;
double a,b,m;
void init()
{
int i,j;
number=0;
for(i=0;i<10005;i++)
{
loop[i].flag=false;
loop[i].num=0;
}
for(i=2;i<10005;i++)
{
if(!loop[i].flag)
{
for(j=i*i;j<10005;j=j+i)
loop[j].flag=true;
}
}
for(i=2;i<10005;i++)
{
if(!loop[i].flag)
{
prime[number]=i;
loop[i].num=number;
number++;
}
}
}
bool judge(int p,int q)
{
double x=p*1.0;
double y=q*1.0;
if(x*y>m)
return false;
if(x/y>1)
return false;
if(x/y<a/b)
return false;
return true;
}
int main()
{
int i,j,d,p,q,max,ansp,ansq;
init();
while(scanf("%lf%lf%lf",&m,&a,&b)!=EOF)
{
if(m==0&&a==0&&b==0)
break;
max=0;
d=int(sqrt(m*b/a));
for(i=d;i>=2;i--)
{
if(!loop[i].flag)
break;
}
int index=loop[i].num;
for(i=0;i<=index;i++)
{
for(j=i;j<=index;j++)
{
p=prime[i];
q=prime[j];
if(judge(p,q)&&p*q>max)
{
max=p*q;
ansp=p;
ansq=q;
}
}
}
printf("%d %d/n",ansp,ansq);
}
return 0;
}