Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

打表TLE,暴力283msAC~~~~~

Posted by lithum at 2009-07-28 17:58:35 on Problem 1411
#include<iostream>
#include<cmath>
using namespace std;

int prime[5200]={0};

int Prime(int t);
int main()
{
	//freopen("input.txt","r",stdin);
	int i,j;
	//int t;
	int m,a,b;
	int upline;
	int w,h;
	while(cin>>m>>a>>b)
	{
		if(m+a+b==0) return 0;
		upline=int( sqrt(double(m*b/a)) );
		w=0; h=0;
		/*
		for(i=0;i<=5133;i++){
			if(prime[i]>upline){
				i--;
				break;
			}
		}
		t=i; h=prime[t1];
		*/
		for(i=0;(Prime(i)<=m/2 && i<=5200 && Prime(i)<=upline);i++){
			for(j=i;(Prime(j)*b>=Prime(i)*a && Prime(j)<=Prime(i));j--){
				if(Prime(i)*Prime(j)<=m && Prime(i)*Prime(j)>w*h){
					w=Prime(j); h=Prime(i);
				}
			}
		}
		cout<<w<<' '<<h<<endl;
	}//end while
	return 0;
}
int Prime(int t)
{
	if(prime[t]>0) return prime[t];
	if(t==0) { prime[0]=2; return 2; }
	int i;
	int tp=Prime(t-1)+1;
	for(i=0;i<t;i++)
	{
		if(tp%Prime(i)==0){
			tp++;
			i=-1;//下一次循环开始时i会++一次从而增加至0
		}
	}
	prime[t]=tp;
	return tp;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator