ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

AOJ 1232 Calling Extraterrestrial Intelligence Again

問題文はこちら↓
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1232


・概要
m,a,bの3つの正の整数が与えられます。(m<100000, a<=1000, b<=1000)
p,qを素数としたとき、
p*q < m かつ a/b <= p/q <= 1の条件を満たすp,qのなかでp*qが最大となるp,qの値を求める問題です。

問題文は英語ですが、詳しく問題内容が書いてあるのでそちらを見た方がよいかもしれません。


・解法
※たぶん実行時間を見る限り、よい解法ではないかもしれません

まずあらかじめ素数表を作っておきます。
そのあとは枝刈りをしつつ、探索していけばよいです。

小数点を含む比較を行うのでEPSを使用します。
(今更ですが、比較するとき割り算ではなく両辺を掛け算したほうが早いですね。 解いてる時思いつかなかった・・・)


ソースコード

#include<iostream>
#include<cmath>
#include<vector>
#include<set>
#define MAX 100000
using namespace std;

#define mp make_pair
static const double EPS = 1e-8;
vector<double> prime;
bool flag[MAX+1];

void eratos(int N){
   for(int i = 0 ; i <= N ; i++)flag[i] = false;
   for(int i = 3 ; i <= N ; i+=2)flag[i] = true;
   prime.push_back(2);
   flag[2]=true;
   
   for(int i = 3 ; i <= N ; i += 2){
      if(!flag[i])continue;
      prime.push_back(i);
      for(int j = i + i ; j <= N ; j+=i)flag[j]=false;
   }
}

double m,a,b,w,h,s;
set<pair<int,int> >st;

void dfs(int i, int j){
   double p = prime[i];
   double q = prime[j];

   if((p*q > m) || (st.find(mp(i,j))!=st.end()))return;
   st.insert(mp(i,j));
   
   if(p*q <= m && p*q > s){
      if((a/b <= p/q || fabs(a/b - p/q) < EPS) && p/q <= 1){
	 s = p*q;
	 w = p;
	 h = q;
      }
   }
   
   if(i==j) dfs(i,j+1);
   else{
      if((a/b <= prime[i+1]/q) || (fabs(a/b  - prime[i+1]/q) < EPS))dfs(i+1,j);
      if((a/b <= p/prime[j+1]) || (fabs(a/b  - p/prime[j+1]) < EPS))dfs(i,j+1);
   }
}

int main(){
   eratos(MAX);
   
   while(cin >> m >> a >> b){
      if(m==0 && a==0 && b==0)break;
      
      st.clear();      
      w = h = s = 0;
      dfs(0,0);
      cout << (int)(w) << " " << (int)(h) << endl;
   }
   return 0;
}