AOJ 1232 Calling Extraterrestrial Intelligence Again
問題
Calling Extraterrestrial Intelligence Again
m, a, bが与えられる。
p*q <= m
a/b <= p/q <= 1
の制約下でp*qが最大となるp,qを答える。
解法
愚直に全探索、実装したらTLE連発した。(http://d.hatena.ne.jp/k_operafan/20110715/1310695379)のシェルソートみたいな探索を初めてしった。
心臓に悪いコード
int m, a, b, tp[50000]; vi p; int getPrime(int sp){ int k[3] = {100, 10, 1}; int w = 0; rep(i, 3){ for(int j = w; j < (int)p.size(); j+=k[i]){ if(sp < p[j]) break; if(p[j]*sp <= m) w = j; else break; } } return p[w]; } int main(){ tp[0] = tp[1] = 1; REP(i, 2, 50000){ if(tp[i]) continue; for(int j = i+i; j < 50000; j += i) tp[j] = 1; } rep(i, 50000){ if(tp[i]) continue; p.PB(i); } while(scanf("%d%d%d", &m, &a, &b) && m){ int resq = 0, resp = 0; for(int i = 0; i < p.size() && p[i] * 2 <= m; i++){ int tq = p[i]; int tp = getPrime(tq); if((double)a/(double)b > (double)tp/(double)tq) continue; if(resq * resp > tp * tq) continue; resq = tq; resp = tp; } printf("%d %d\n", resp, resq); } return 0; }