2942181_ac_109ms_424k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include "stdio.h"
#include "math.h"
#include "string.h"
#include <algorithm>

using namespace std;

struct node
{
	int n;
	int p, q;
}num[24001];
int prime[10000];
int no, nn;

int isprime(int n)
{
	int i, t;

	t = (int)sqrt(n);
	for(i = 3; i <= t; i+=2)
		if(n%i==0)
			return 0;
	return 1;
}

bool cmp(node a,node b)
{
	return a.n>b.n;
}

void init()
{
	int i, j;
	int t;

	prime[0] = 2;
	prime[1] = 3;
	no = 2;
	for(i = 5; i < 50000; i += 2)
	{
		if(isprime(i))
			prime[no++] = i;
	}
	nn = 0;
	for(i = 0; i < no; i++)
	{
		if(prime[i]>316)
			break;
		for(j = i; j < no; j++)
		{
			t = prime[i]*prime[j];
			if(t>=100000)
				break;
			num[nn].n = t;
			num[nn].p = prime[i];
			num[nn++].q = prime[j];
		}
	}
	sort(num,num+nn,cmp);
}

int gcd(int a,int b)
{
	int r;
	
	while(b)
	{
		r = a%b;
		a = b;
		b = r;
	}
	return a;
}

int main()
{
	int m, a, b, t, i;

	init();
	while(scanf("%d%d%d",&m,&a,&b)==3)
	{
		if(a==0&&b==0&&m==0)
			break;
		t = gcd(a,b);
		a /= t;b /= t;
		for(i = 0; i < nn; i++)
		{
			if(num[i].n<=m&&num[i].p*b>=a*num[i].q)
			{
				printf("%d %d\n",num[i].p,num[i].q);
				break;
			}
		}
	}
	return 0;
}