| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
二分有點慢+1。。。16ms,擠进1024名纪念#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator