概要
分数 が与えられる。
分母が n を超えない既約分数のうち、 との差の絶対値が最も小さいものを求めよ。
解法
分母を決めると、分子とその分数の大きさは単調性を持ちます。
従って、分子を二分探索することができます。
コード
#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i ) int solve_bs( int x, int y, int b ) { double target = (double)x / y; int lb = 0, ub = 1000000; REP( t, 0, 100 ) { int a = ( lb + ub ) / 2; if ( (double)a / b < target ) { lb = a; } else { ub = a; } } int res; double diff = DBL_MAX; REP( a, lb - 10, ub + 10 ) { double d = abs( (double)x / y - (double)a / b ); if ( d < diff ) { res = a; diff = d; } } return res; } int main() { cin.tie( 0 ); ios::sync_with_stdio( false ); int x, y, n; cin >> x >> y >> n; int resa, resb; double diff = DBL_MAX; REP( b, 1, n + 1 ) { int a = solve_bs( x, y, b ); double d = abs( (double)x / y - (double)a / b ); if ( d < diff ) { resa = a; resb = b; diff = d; } } cout << resa << '/' << resb << endl; return 0; }