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