AOJ 1208 Rational Irrationals
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1208
p^(1/2)に最も近い有理数で、x/y>p^(1/2)、u/v
#define F first #define S second typedef pair<int,int> PI; #define mp(a,b) make_pair(a,b) main(){ int n,p; while(cin>>p>>n,n|p){ PI xy=mp(p,1),uv=mp(0,1); for(int i=1;i<=n;i++){ for(int j=max(1,int(i/sqrt(p)-1));j<=min(n,int(i/sqrt(p)+2));j++){ if(__gcd(i,j)>1)continue; if(i*i<p*j*j && j*uv.F<uv.S*i)uv=mp(i,j); if(i*i>p*j*j && xy.F*j>i*xy.S)xy=mp(i,j); } } cout<<xy.F<<'/'<<xy.S<<' '<<uv.F<<'/'<<uv.S<<endl; } }