AOJ 1208 - Rational Irrationals

問題概要

nとpが与えられる。
1~nまでの数字で分子と分母を作ったとき、x/y > √p > u/vとなる最小のx/yと最大のu/vを分数の形で出力せよ。出力する分数は既約分数である必要がある。

制約

• n < 10000
• p < 10000

解法

√pより大きくなる分数、小さくなる分数それぞれについて分母を決めて分子を二分探索する。

コード

#include <bits/stdc++.h>

using namespace std;

#define INF 1e9

class Fraction{
public:;
  double numerator,denominator;
  double div();
};

double Fraction::div(){
  return numerator/denominator;
}

ostream &operator << (ostream &os,const Fraction &f){
  os << f.numerator << '/' << f.denominator;
  return os;
}

int main(){
  double p;
  int n;
  while(cin >> p >> n, p){
    p = sqrt(p);
    Fraction a = (Fraction){-1,1};
    Fraction b = (Fraction){INF,1};
    for(int den = 1 ; den <= n ; den++){
      int l = 0, r = n+1;
      while(l < r){
        double mid = (l + r) / 2;
        if(mid < p*den){
          if(mid/den > a.div()){
            a = (Fraction){mid,den};
          }
          l = mid+1;
        }else{
          r = mid;
        }
      }
      l = 0, r = n+1;
      while(l < r){
        double mid = (l + r) / 2;
        if(mid > p*den){
          if(mid/den < b.div()){
            b = (Fraction){mid,den};
          }
          r = mid;
        }else{
          l = mid+1;
        }
      }
    }
    cout << b << " " << a << endl;
  }
  return 0;
}