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

二分有點慢+1。。。16ms,擠进1024名纪念

Posted by KatrineYang at 2016-09-28 12:40:34 on Problem 1411 and last updated at 2016-09-28 12:41:56
#include <iostream>
#include <stdio.h>
#include <cmath>
using namespace std;

int primes[1229];

int primes50000[10000];
int primeCnt = 1229;

inline int mn(int a, int b){return (a>b) ? b : a;}

void getPrimeList(){
	for(int i = 0; i < 1229; i++) primes50000[i] = primes[i];
	for(int j = 10001; j < 50000; j+=2){
		for(int k = 1; ; k++){
			if(primes[k]*primes[k]>j){
				primes50000[primeCnt] = j;
				primeCnt++;
				break;
			}
			if(!(j%primes[k])) break;
		}
	}
}

int findPrime(int thres){
	int lower = 0, upper = primeCnt-1;
	while(lower < upper){
		int mid = (lower + upper+1)/2;
		if(primes50000[mid] > thres){
			upper = mid-1;
		}
		else{
			lower = mid;
		}
	}
	return lower;
}

int m,a,b;

int main() {
	//printf("%d", primes[1228]);
	getPrimeList();
	//printf("%d", primeCnt);
	while(1){
		scanf("%d%d%d", &m, &a, &b);
		if(!m) return 0;
		int mx = 0;
		int argp, argq;
		int thres = mn(m/2, (int)sqrt(m*b*1.0/a));
		int q = findPrime(thres), p;
		double alpha = a*1.0/b;
		for(; q>=0; q--){
			if(primes50000[q]*primes50000[q]<mx) break;
			p = mn(q, findPrime(m/primes50000[q]));
			if(primes50000[p]>=alpha*primes50000[q] && primes50000[p]*primes50000[q]<=m){
				int tmp = primes50000[p]*primes50000[q];
				if(tmp > mx) {
					mx = tmp;
					argp = primes50000[p];
					argq = primes50000[q];
				}
			}
		}
		printf("%d %d\n", argp, argq);
	}
	return 0;
}

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