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

Ordered fractions 题号:71 难度: 10 中英对照

Consider the fraction, n/d, where n and d are positive integers. If n<d and HCF(n,d)=1, it is called a reduced proper fraction.

If we list the set of reduced proper fractions for d ≤ 8 in ascending order of size, we get:

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

It can be seen that 2/5 is the fraction immediately to the left of 3/7.

By listing the set of reduced proper fractions for d ≤ 1,000,000 in ascending order of size, find the numerator of the fraction immediately to the left of 3/7.

Solution

分析题意,我们的目标是给定范围$N$找到最大的分数$x= \frac{p}{q}$,使得 $$ x< t = \frac{a}{b}= \frac{3}{7},0 < t <1,b \leq N $$ 一般暴力做法是找到所有满足条件的分数 $\frac{p}{q} < t,q \leq N$,然后舍弃掉所有不是*reduced proper fraction* 的数,找到其中最大的那个,但是暴力破解方法的复杂度近似 $O=tN^2$,对于我们的问题中, $N=1000000$,需要遍历近 $2.1 \times 10^{11}$个分数,所以**暴力求解法**不可取。 分析问题,可知: 对于分母$q$,我们考虑一个分数,最大的分子是$p$,且这个分数满足 $\frac{p}{q}< \frac{a}{b} $,做变换得到 $$ \frac{p}{q}< \frac{a}{b} \Longleftrightarrow p \cdot b < q \cdot a \Longleftrightarrow p \cdot b \leq q \cdot a-1 \Longleftrightarrow p \leq \lfloor \frac{q \cdot a-1}{b} \rfloor $$ 设$v(q) = \lfloor \frac{q \cdot a-1}{b} \rfloor , q \leq N$ ,所以 $\frac{v(q)}{q}$ 是在小于$t$时有最大分母$q$。 根据以上分析得到下面伪代码: ![psecode](http://i1.piimg.com/588926/d4ec72fa569c79ce.png) 虽然这里求出了最大的分母,但是它并不一定满足*reduced proper fraction*,即要满足 $HCF(p,q) = 1$ 首先我们知道分数的分母越大,固定分母时,它和它邻近的分数的距离越小。所以要寻找最接近的分数,它的分母肯定足够大,所以从最大的分母开始往小分母遍历$(N-1, N-2,\cdots,q,\cdots)$,那么如何跳出遍历循环呢? 对分数 $\frac{r}{s} < \frac{a}{b}$,它们间距离表示为: $$ \frac{r}{s} - \frac{a}{b} = \frac{a \cdot s - b \cdot r}{b \cdot s} \geq \frac{1}{b \cdot s} $$ 当目前找到最大的分数为$\frac{p}{q} $,比当前与目标距离还近的数 $\frac{r}{s}$ 要满足 $$ \frac{1}{b \cdot s} < \frac{a \cdot q - b \cdot p}{b \cdot q} $$ 等价于 $$ s > \frac{ q}{a \cdot q - b \cdot p} $$ 因此,每一个最大值都给出一个很小的范围来确定分母,设 $\delta = a \cdot q - b \cdot p$ . - 当$\delta = 1$时,每个离目标更近的数必须满足分母 $s>q$,由于是从大到小遍历,$q \sim N$都已经遍历过,所以我们可以直接得出结论$\frac{p}{q} $就是离目标最近的数; - 当$\delta > 1$时,对分母有小的边界 $\frac{q}{\delta}$,这时很快也能遍历完。 程序伪代码如下: ![psecode2](http://i2.muimg.com/588926/fabd1ec57f489b5e.png) 这样根据以上思想得到的结果就是满足*reduced proper fraction* 的最大分母。

Code

public final class p71 {
    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" );
    }

//    取值范围
    private  static int N = 1000000;
    private static int a = 3;
    private static int b = 7;

    static public String run(){
        int bestN = 0;
        int bestD = 1;
        int curD = N;
        int minD = 1;
        int curN,delta;
        while(curD >= minD){
            curN=( curD * a -1)/ b;
            if ( (long)bestN * curD < (long)curN * bestD ) {
                bestN = curN;
                bestD = curD;
                delta = a *curD - b*curN;
                minD = curD /(delta+1);
            }
            curD -= 1;
        }
        return Integer.toString(bestN);
    }
}
428570
6ms