読者です 読者をやめる 読者になる 読者になる

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;
}