AOJ1208 Rational Irrationals

問題リンク Rational Irrationals

• 概要

正の整数p, nが与えられる。ここで、Qnをn以下の正の整数を使って表せる有理数の集合とする。Qnに属するものの中で√pより小さくて最大のものu/vと、√pより大きくて最小のものx/yを答えよ。

• 解法

1/1から始めていき、√pに近づくように分母と分子を変えていきます。√pより小さければ分子を+1し、そうでなければ分母を+1します。分母と分子が共にn以下の間続け、u/vとx/yを更新していきます。

• ソース

import java.util.Scanner;

//Rational Irrationals
public class AOJ1208 {

	static long gcd(long a, long b){
		if(a < b){
			long tmp = a;
			a = b;
			b = tmp;
		}
		while(b!=0){
			long r = a%b;
			a = b;
			b = r;
		}
		return a;
	}

	void run(){
		Scanner sc = new Scanner(System.in);
		while(true){
			int p = sc.nextInt();
			int n = sc.nextInt();
			if((p|n)==0)break;
			double rp = Math.sqrt(p);
			int num = 1;
			int den = 1;
			boolean up = true;
			int x, y, u, v;
			x = y = u = v = 0;
			double d1, d2;
			d1 = -n;
			d2 = n;
			while(num<=n&&den<=n){
				double d = num*1.0/den-rp;
				if(d<0){
					up = true;
					if(d1<d&&gcd(num,den)==1){
						d1 = d;
						u = num;
						v = den;
					}
				}
				else{
					up = false;
					if(d<d2&&gcd(num,den)==1){
						d2 = d;
						x = num;
						y = den;
					}
				}
				num += up?1:0;
				den += up?0:1;
			}
			System.out.println(x+"/"+y+" "+u+"/"+v);
		}
	}

	public static void main(String[] args) {
		new AOJ1208().run();
	}
}