關(guān)于啥是Project Euler 詳見 https://projecteuler.net/about????

觀前聲明：? ? ? ? ? ?

1. 這是個人興趣使然的對自己入坑pe的記錄，僅提供思路和部分代碼；各個方面肯定都是有著優(yōu)化與提升空間的，甚至在許多大佬看來這應(yīng)該是初學(xué)者的淺薄而未經(jīng)剪枝的丑碼，如果能幫到有興趣的人自是最好，也歡迎能醍醐灌頂?shù)纳疃扔懻摗??

2. 大佬看到了笑笑就行，還請輕噴。

3. 帶著惡意，抬杠者...俺也噴不過您，也不能拿您咋樣...畢竟這只是我個人興趣使然的行為或者說是學(xué)習(xí)記錄分享。?（說是記錄，但因為是早先寫的所以其實是在各種意義上公開處刑和吐槽自己 并嘗試補救優(yōu)化）

4. 語言是c++，用的VS平臺

前排：本期是有關(guān)分?jǐn)?shù)排序的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的既約真分?jǐn)?shù)，當(dāng)d<=8時，把所有的真分?jǐn)?shù)按從小到大排列可以得到如下：

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的最大既約真分?jǐn)?shù)為2/5

那么當(dāng)d?≤ 1000000時，找到不大于3/7的最大既約真分?jǐn)?shù)的分子。

先說個暴搜的思路：

大概思路是用一個函數(shù)，對于一個特定的d，找到最大的i使i/d<3/7

然后在主函數(shù)中從d=2開始跑到d=1000000，找到最大的(double)di/d

di即為所求

暴搜過了后發(fā)現(xiàn)這道題其實是著名的Farey Sequence（詳細(xì)請自行搜索）

這個數(shù)列有一個有趣的性質(zhì)：

對于其中任意三個連續(xù)的分?jǐn)?shù)，假設(shè)第一個分?jǐn)?shù)為a/b，第三個分?jǐn)?shù)為c/d，則夾在中間的分?jǐn)?shù)為(a+c)/(b+d)。

比如在3/8和3/7中，夾在中間的分?jǐn)?shù)為(3+3)/(7+8)=6/15=2/5

增大d相當(dāng)于繼續(xù)上述的迭代過程

2/5與3/7的中間分?jǐn)?shù)為5/12，5/12與3/7的中間分?jǐn)?shù)為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āng)d?≤ 8時有21個既約真分?jǐn)?shù)

那么d?≤ 1,000,000時有多少個？

實際上，這題可以用69題的歐拉函數(shù)做

考慮i=1~d，若i/d為既約真分?jǐn)?shù)，則HCF(i,d)=1（最大公因數(shù)為1）

所以以d為分母的既約真分?jǐn)?shù)的個數(shù)就是 φ(d)個? ?

主函數(shù)令d從2跑到1000000將所有的phi[d]加起來即可。

(歐拉函數(shù)篩表相關(guān)代碼見69題)

（官方同樣也給了一個這題的overview：https://projecteuler.net/overview=072? 內(nèi)有關(guān)于計算歐拉函數(shù)前n項和的方法及歐拉函數(shù)的一些性質(zhì)）

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內(nèi)有3個分?jǐn)?shù)

那么d?≤ 12000時1/3到1/2內(nèi)有多少個分?jǐn)?shù)？

實際上這題我啥方法都沒用..第一個思路就是純暴搜過的

利用同余定理

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++

因為規(guī)模不大很快就跑完了

（官方同樣也給了一個這題的overview：https://projecteuler.net/overview=073)

如果有想知道更精細(xì)巧妙地解法的同學(xué)不妨一閱

ans：7295372

今日三道題難度為10% 20% 15%

后面的76 77 78會構(gòu)成一個系列想放一起；但無關(guān)的散題74 75，2題單獨做一期會不會太水了呢...

放張圖做封面...