SRM 246 DIV1 Hard CalcRoot

SRM

問題 Editorial

問題

abs(sqrt(N) - a/b)が最小となる正整数a, b (b <= D)を求めよ

  • 1 <= N <= 1000000
  • 1 <= D <= 1000

解答

long doubleでやるだけ。
最小との比較は整数演算だけでもできるらしい(Editorial参照)

コメント

簡単回。
最小との比較の誤差を何も気にせずに書いてた。それ駄目だろ！まあlong doubleでよかったけど

コード

#include <string>
#include <sstream>
#include <cmath>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
using namespace std;
typedef long double ld;
template<typename T>T gcd_positive(T x, T y) { return y == 0 ? x : gcd_positive(y,x%y); }
struct CalcRoot {
	string approximate(int N, int D) {
		ld s = sqrt(N*1.L);
		ld me = 1e99; int mn, md;
		rer(d, 1, D) rep(i, 3) {
			int n = (int)(s * d + (i * 0.5));
			ld e = abs(n * 1.L / d - s);
			if(e < me) mn = n, md = d, me = e;
		}
		int g = gcd_positive(mn, md);
		mn /= g; md /= g;
		stringstream ss;
		ss << mn << "/" << md;
		return ss.str();
	}
};