关于啥是Project Euler 详见 https://projecteuler.net/about    

观前声明：           

1. 这是个人兴趣使然的对自己入坑pe的记录，仅提供思路和部分代码；各个方面肯定都是有着优化与提升空间的，甚至在许多大佬看来这应该是初学者的浅薄而未经剪枝的丑码，如果能帮到有兴趣的人自是最好，也欢迎能醍醐灌顶的深度讨论。  

2. 大佬看到了笑笑就行，还请轻喷。

3. 带着恶意，抬杠者...俺也喷不过您，也不能拿您咋样...毕竟这只是我个人兴趣使然的行为或者说是学习记录分享。 （说是记录，但因为是早先写的所以其实是在各种意义上公开处刑和吐槽自己 并尝试补救优化）

4. 语言是c++，用的VS平台

前排：本期是有关分数排序的3道.

Ordered fractions

Problem 71

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.

考虑形如n/d的既约真分数，当d<=8时，把所有的真分数按从小到大排列可以得到如下：

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

不大于3/7的最大既约真分数为2/5

那么当d ≤ 1000000时，找到不大于3/7的最大既约真分数的分子。

先说个暴搜的思路：

大概思路是用一个函数，对于一个特定的d，找到最大的i使i/d<3/7

然后在主函数中从d=2开始跑到d=1000000，找到最大的(double)di/d

di即为所求

暴搜过了后发现这道题其实是著名的Farey Sequence（详细请自行搜索）

这个数列有一个有趣的性质：

对于其中任意三个连续的分数，假设第一个分数为a/b，第三个分数为c/d，则夹在中间的分数为(a+c)/(b+d)。

比如在3/8和3/7中，夹在中间的分数为(3+3)/(7+8)=6/15=2/5

增大d相当于继续上述的迭代过程

2/5与3/7的中间分数为5/12，5/12与3/7的中间分数为8/19...

于是可得2/5  5/12  8/19  11/26  14/33  ...  (2+3k)/(5+7k) ...  3/7

d ≤ 1000000，即5+7k≤ 1000000，k最大值为142856

代入(2+3k)/(5+7k)，可得428570/999997。

（官方也给了一个这题的overview：https://projecteuler.net/overview=071）

ans：428570

Counting fractions

Problem 72

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 there are 21 elements in this set.

How many elements would be contained in the set of reduced proper fractions for d ≤ 1,000,000?

Farey Sequence  当d ≤ 8时有21个既约真分数

那么d ≤ 1,000,000时有多少个？

实际上，这题可以用69题的欧拉函数做

考虑i=1~d，若i/d为既约真分数，则HCF(i,d)=1（最大公因数为1）

所以以d为分母的既约真分数的个数就是 φ(d)个   

主函数令d从2跑到1000000将所有的phi[d]加起来即可。

(欧拉函数筛表相关代码见69题)

（官方同样也给了一个这题的overview：https://projecteuler.net/overview=072  内有关于计算欧拉函数前n项和的方法及欧拉函数的一些性质）

ans：303963552391

Counting fractions in a range

Problem 73

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 there are 3 fractions between 1/3 and 1/2.

How many fractions lie between 1/3 and 1/2 in the sorted set of reduced proper fractions for d ≤ 12,000?

d ≤ 8时Farey Sequence中，1/3到1/2内有3个分数

那么d ≤ 12000时1/3到1/2内有多少个分数？

实际上这题我啥方法都没用..第一个思路就是纯暴搜过的

利用同余定理

n从1到12000，d从1到12000，sum初始为0

如果hcf(d,n)=1，且1/3<n/d<1/2（3 * n > d && 2 * n < d） 那么让sum++

因为规模不大很快就跑完了

（官方同样也给了一个这题的overview：https://projecteuler.net/overview=073)

如果有想知道更精细巧妙地解法的同学不妨一阅

ans：7295372

今日三道题难度为10% 20% 15%

后面的76 77 78会构成一个系列想放一起；但无关的散题74 75，2题单独做一期会不会太水了呢...

放张图做封面...