当前位置:首页 » Project Euler » 详细页

Best Approximations 题号:192 难度: 75 中英对照

Let x be a real number.
A best approximation to x for the denominator bound d is a rational number r/s in reduced form, with sd, such that any rational number which is closer to x than r/s has a denominator larger than d:

|p/q-x| < |r/s-x| ⇒ q > d

Solution

Farey数列是一个在区间$[0,1]$的最简分数序列,且容易看出除了$0$和$1$以外都是真分数,这个序列包括所有分母不超过给定数字$k$的最简分数且从小到大排列,记为$F[k]$,为表述方便,$0$和$1$一般表示为$0/1$和$1/1$,例如: $$F[1]=\{0/1,1/1\}$$ $$F[2]=\{0/1,1/2,1/1\}$$ $$F[3]=\{0/1,1/3,1/2,2/3,1/1\}$$ $$F[4]=\{0/1,1/4,1/3,1/2,2/3,3/4,1/1\}$$ $$F[5]=\{0/1,1/5,1/4,1/3,2/5,1/2,3/5,2/3,3/4,4/5,1/1\}$$ $$……$$ Farey数列有三个很重要的基本性质: 1. $a/b$和$c/d$是某个$F[k]$数列的相邻两项,当且仅当$bc-ad=1$ 2. 若$bc-ad=1$,则处于$a/b$和$c/d$之间的分母最小的分数是$(a+c)/(b+d)$,且不能约分,且是唯一的,即这个区间中不存在其他以$b+d$为分母的分数 3. 若$a/b< c/d< e/f$是某个$F[k]$数列的连续三项,则$c/d=(a+e)/(b+f)$ 直接暴力计算每一个$F[k]$,判断$\sqrt{n}$的小数部分在哪一部分,继续枚举该部分即可,此处复杂度是$O(logn)$的。

Code

import java.math.BigInteger;

public final class p192 {
    public static void main(String[] args) {
        long start=System.nanoTime();
        String result = run();        
        long end=System.nanoTime();
        System.out.println(result);
        System.out.println( (end-start)/1000000 + "ms" );
    }


    static public String run() {
    	BigInteger ans=BigInteger.ZERO;
    	for(int i=2;i<=100000;i++){
    		ans=ans.add(solve(i));
    	}
		return ans.toString();
    }
    

    static BigInteger LIMIT=BigInteger.valueOf(1000000000000L);
    
    
    static BigInteger solve(long n){
    	long m=(long)Math.sqrt(n);
    	if(m*m==n) return BigInteger.ZERO;
    	return solve(BigInteger.valueOf(n),BigInteger.valueOf(m));
    }
    
    static BigInteger solve(BigInteger n,BigInteger m){
    	BigInteger Lp=BigInteger.ZERO,Lq=BigInteger.ONE,Rp=BigInteger.ONE,Rq=BigInteger.ONE;
    	while(true){
        	BigInteger p=Lp.add(Rp);
        	BigInteger q=Lq.add(Rq);
    	//	System.out.println((p.add(q.multiply(m)))+"/"+q);
        	if(q.compareTo(LIMIT)>0)
        		break;
        	int com=sqr(p.add(m.multiply(q)))
        			.compareTo(q.multiply(q).multiply(n));
        	if(com<0){
        		Lp=p;Lq=q;
        	}else if(com>0){
        		Rp=p;Rq=q;
        	}else{
        		return q;
        	}
    	}

		if(n.multiply(sqr(BigInteger.valueOf(2).multiply(Rq.multiply(Lq))))
				.compareTo(
						sqr(BigInteger.valueOf(2).multiply(Rq.multiply(Lq)).multiply(m).add(Rp.multiply(Lq).add(Lp.multiply(Rq))))
						)<0)
			return Lq;
		return Rq;
    }
    static BigInteger sqr(BigInteger x){
    	return x.multiply(x);
    }


}
57060635927998347
15506ms