1239 calling extraterrestrial intelligence again.cpp

威士忌的HDU题解.大概有260多题的源码。对于学习非常有好处。

//总算poj，zoj，hdoj 全过了 
#include <cstdio>
#include <cmath>
using namespace std;
int m,a,b;
int prime[1300];

/************筛选法求素数_改进***************/
int sievePrime_2(int savenum[],int n)
{
    int ca,temp,now;
    int num[5000]={0};
    savenum[0]=2;now=1;

    for(ca=3;ca<=n;ca+=2)
    {
        if(num[(ca-1)/2]==0)
        {
            temp=ca+ca;
            while(temp<=n)
            {
                if(temp%2!=0)
                    num[(temp-1)/2]=1;
                temp+=ca;
            }
        }
    }

    for(ca=3;ca<=n;ca+=2)
        if(num[(ca-1)/2]==0)
        {   savenum[now]=ca;now++;}

    return now-1;
}
/*********二分查找-返回就近位置********************/
int divFind(int num[],int findnum,int size)
{
    int low=1,high=size,mid;
    while(high>=low)
    {
        mid=(low+high)/2;
        if(num[mid]==findnum)
            return mid-1;
        else
        {
            if(num[mid]>findnum)
            {   
            	high=mid-1;
            	if(num[high] < findnum)
            		return high;
			}
            else
            {   
            	low=mid+1;
            	if(num[low] > findnum)
            		return low-1;
			}
        }
    }
}
int main()
{
	int i,j,n,psize,p,q,t,pos,lmax;
	double rate;
	
	psize=sievePrime_2(prime,10000);
	while( scanf("%d %d %d",&m,&a,&b)!=EOF )
	{
		if(m==0 && a==0 && b==0)
			break;
		rate=(double)a/b;
		lmax=0;
		pos=divFind(prime,(int)sqrt((double)m),psize)-1;
		for(i=pos ;i<=psize; i++)
		{
			if(prime[i]>m)
				break;
			for(j=divFind(prime,(int)rate*prime[i],psize)-1 ;j<=i; j++)
			{
				if( prime[i]*prime[j]>m)
					break;
				if(((double)prime[j]/prime[i])<rate )
					continue;
				if(lmax<prime[i]*prime[j])
				{
					lmax=prime[i]*prime[j];
					q=prime[i];p=prime[j];
				}
			}
		}
		printf("%d %d\n",p,q);
	}
	return 0;
}