Problem 71：Ordered fractions

Problem 71：Ordered fractions

题目链接：http://static.projecteuler.net/problem=71

题目大意：将所有形如$frac{n}{d}(d leqslant 1,000,000)$的最简真分数按大小升序排列，求此时$frac{3}{7}$直接左邻的分数的分子。

法里数列

$n$阶法里数列是$0$和$1$之间最简分数的数列，由小至大排列，每个分数的分母不大于$n$。

设$F_n$为$n$阶法里数列，则有如下性质：

• $|F_n|=|F_{n-1}|+varphi (n)$.

因为$F_n$仅比$F_{n-1}$多了$E={frac{p}{n}:(p,n)=1}$，其中$|E|=varphi (n)$。由$|F_1|=2，$可推出$|F_n|=1+sum_{i=1}^n varphi(n)$.

• 若$frac{a}{b}$和$frac{c}{d}$是某$k$阶法里数列的相邻项，且$frac{a}{b} < frac{c}{d}$，则它们之差为$frac{1}{bd}$，也就是说$bc-ad=1$。反之同样成立：若$frac{a}{b}$，$frac{c}{d}$均为真分数，且$frac{a}{b} < frac{c}{d}$，$bc-ad=1$，则有$frac{a}{b}$和$frac{c}{d}$在$k$阶法里数列中是邻项，$k=max{b,d}$.
• 若$frac{a}{b}$和$frac{c}{d}$是某$k$阶法里数列的相邻项，随着$k$增大，$frac{a}{b}$和$frac{c}{d}$间出现的第一项为$frac{a+c}{b+d}$.

这里用到了法里数列的第三条性质。

代码如下：

#include <iostream>
using namespace std;
int main(void){
    int a=2,b=5;
    while(b+7<=1000000){
        a+=3;
        b+=7;
    }
    cout<<a;
}