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

觀前聲明：? ? ???

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

2. 大佬看到了笑笑就行，還請(qǐng)輕噴。

3. 帶著惡意，抬杠者...俺也噴不過(guò)您，也不能拿您咋樣...畢竟這只是我個(gè)人興趣使然的行為或者說(shuō)是學(xué)習(xí)記錄分享。?（說(shuō)是記錄，但因?yàn)槭窃缦葘?xiě)的所以其實(shí)是在各種意義上公開(kāi)處刑和吐槽自己 并嘗試補(bǔ)救優(yōu)化）

4. 語(yǔ)言是c++，用的VS平臺(tái)

Maximum path sum II

Problem 67

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3
7?4
2?4?6
8 5?9?3

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom in?triangle.txt?(right click and 'Save Link/Target As...'), a 15K text file containing a triangle with one-hundred rows.

NOTE:?This is a much more difficult version of?Problem 18. It is not possible to try every route to solve this problem, as there are 299?altogether! If you could check one trillion (1012) routes every second it would take over twenty billion years to check them all. There is an efficient algorithm to solve it. ;o)

（triangle.txt：https://projecteuler.net/project/resources/p067_triangle.txt）

問(wèn)題與pe18：Maximum path sum I 同出一轍，只是數(shù)據(jù)不一樣了而已

解法在pe18題已經(jīng)給出. 經(jīng)典動(dòng)態(tài)規(guī)劃題。

ans：7273

Magic 5-gon ring

Problem 68

Consider the following "magic" 3-gon ring, filled with the numbers 1 to 6, and each line adding to nine.

Working?clockwise, and starting from the group of three with the numerically lowest external node (4,3,2 in this example), each solution can be described uniquely. For example, the above solution can be described by the set: 4,3,2; 6,2,1; 5,1,3.

It is possible to complete the ring with four different totals: 9, 10, 11, and 12. There are eight solutions in total.

Total? ? ? ? ? ? ? ? ??Solution Set

9? ? ? ? ? ? ? ? ? ? ? ? ?4,2,3; 5,3,1; 6,1,2

9? ? ? ? ? ? ? ? ? ? ? ? ?4,3,2; 6,2,1; 5,1,3

10? ? ? ? ? ? ? ? ? ? ? ?2,3,5; 4,5,1; 6,1,3

10? ? ? ? ? ? ? ? ? ? ? ?2,5,3; 6,3,1; 4,1,5

11? ? ? ? ? ? ? ? ? ? ? ?1,4,6; 3,6,2; 5,2,4

11? ? ? ? ? ? ? ? ? ? ? ?1,6,4; 5,4,2; 3,2,6

12? ? ? ? ? ? ? ? ? ? ? ?1,5,6; 2,6,4; 3,4,5

12? ? ? ? ? ? ? ? ? ? ? ?1,6,5; 3,5,4; 2,4,6

By concatenating each group it is possible to form 9-digit strings; the maximum string for a 3-gon ring is 432621513.

Using the numbers 1 to 10, and depending on arrangements, it is possible to form 16- and 17-digit strings. What is the maximum?16-digit?string for a "magic" 5-gon ring?

在一個(gè)3-gon ring中填上數(shù)字1~6，使得每條線的和相等。若這個(gè)和為9，從最小的外圈開(kāi)始以順時(shí)針將3條線逐一列出 可以形成?4,3,2; 6,2,1; 5,1,3? ：

若以432621513代表其得到的數(shù)字，那么3-gon ring能得到的最大數(shù)字是432621513

考慮5-gon ring 填上數(shù)字1~10，它能得到16或17位數(shù)字（若數(shù)字10作為中間位則能得到17位數(shù)字，不然得到的是16位），那么5-gon ring能得到的最大的16位數(shù)字是多少

這道題是能夠手算的，因?yàn)橐玫?6位，即10在外圈，又要滿足最大情況，只要考慮外圈都是較大的數(shù)字如6 7 8 9 10，內(nèi)圈都是較小的數(shù)字1 2 3 4 5

并注意到6+7+8+9+10+2(1+2+3+4+5)=70? 即每條線和為14

稍加觀察不難發(fā)現(xiàn)653? ?725? 842? ?914? ?1031? 恰好能滿足

（考慮的時(shí)候要按6 10 9 8 7的順序考慮并且時(shí)刻注意滿足最大數(shù)）

排列一下就是6531031914842725。

但這題也能暴搜出來(lái)，我使用了看著最丑的for的寫(xiě)法，在一個(gè)長(zhǎng)度為10數(shù)組里，

寫(xiě)了9個(gè)for(A[i])....但是只要條件限制的夠多? 這樣暴搜也不慢

因?yàn)闆](méi)有任何技巧性就不放了.

ans：6531031914842725

Totient maximum

Problem 69

Euler's Totient function, φ(n) [sometimes called the phi function], is used to determine the number of numbers less than?n?which are relatively prime to?n. For example, as 1, 2, 4, 5, 7, and 8, are all less than nine and relatively prime to nine, φ(9)=6.

It can be seen that?n=6 produces a maximum?n/φ(n) for?n?≤ 10.

Find the value of?n?≤ 1,000,000 for which?n/φ(n) is a maximum.

歐拉函數(shù)φ(n)表示：對(duì)正整數(shù)n，小于或等于n的數(shù)中與n互質(zhì)的數(shù)的數(shù)目。

比如6，這樣的數(shù)有1，5，所以φ(6)=2? ?6/φ(6)=3

找到1000000以內(nèi)的n使得n/φ(n)取到最大值。

表面上來(lái)看? 利用同余定理驗(yàn)證是否互質(zhì)來(lái)計(jì)算歐拉函數(shù)再跑個(gè)1000000的暴搜也不是不行，大概10min

（同余定理的一個(gè)結(jié)論：a%b=(b%(a%b))（a>=b） 證明自行翻閱數(shù)論吧）

代碼可寫(xiě)成：

int gcd(int a,int b)

{

? ? ? ? return b?gcd(b,a%b):a;

}

long long fain2(long long n)

{

? ? ? ?long long i, sum = 0;

? ? ? ?for (i = 1; i < n; i++)

? ? ? ? ? ? ?if (gcd(n, i) == 1)sum++;

? ? ? ?return sum;

}

但這里我們采用更聰明的寫(xiě)法，利用歐拉函數(shù)本身的性質(zhì)直接得到一個(gè)歐拉函數(shù)值得表，儲(chǔ)存在phi[]數(shù)組中。

歐拉函數(shù)的3個(gè)性質(zhì)：

性質(zhì)① m是素?cái)?shù)時(shí)，有φ(m)=m-1

性質(zhì)② 當(dāng)m、n互素時(shí)，φ(m*n)=φ(m)*φ(n)

性質(zhì)③ 對(duì)一切正整數(shù)n，有φ(p^n)=[p^(n-1)]*(p-1) （p為質(zhì)數(shù)）??

（證明請(qǐng)自己嘗試或查閱資料）

利用篩子先跑一個(gè)質(zhì)數(shù)表儲(chǔ)存在數(shù)組prime[]中(prime[i]=0代表i是質(zhì)數(shù)，另外再用一個(gè)bprime[]數(shù)組按順序儲(chǔ)存質(zhì)數(shù))，對(duì)于phi[i]，如果i是個(gè)質(zhì)數(shù)，那么phi[i]=i-1，如果i是個(gè)合數(shù)，那么小于i的所有質(zhì)數(shù)的倍數(shù)i *?bprime[j]滿足phi[i * bprime[j]] = phi[i] * ?phi[bprime[j]]（性質(zhì)2）

并且值得注意的是如果bprime[j]是i的質(zhì)因子，那么：

phi[i *?bprime[j]] = phi[i] *?bprime[j]（即若m,n是正整數(shù),m|n,則φ(mn)=mφ(n)）

（事實(shí)上比較2者定義：phi(n) 是 1 到 n 中與n 互素的數(shù)的個(gè)數(shù).phi(mn) 是 1 到 mn 中與 mn 互素的數(shù)的個(gè)數(shù)即可證明）

關(guān)于32行的break 是為了避免重復(fù)運(yùn)算，舉個(gè)例子：

i = 8，j=1，bprime[j] = 2，如果不跳出循環(huán)，prime[j+1]=3，8*3=2*4*3=2*12，在i=12時(shí)會(huì)計(jì)算。因?yàn)闅W拉篩法的原理便是通過(guò)最小素因子來(lái)消除。

主函數(shù)跑一遍找最大的n/(double)phi[n]就行了

評(píng)論區(qū)也有不少手算的大佬. 摘一個(gè)大佬的思路：

if n has the factor 2 every 2nd number will not be relatively prime to n

if n has the factor 3 every 3rd number will not be relatively prime to n

and so on....

for phi(n) to be as small as posible to make n/phi(n) maximal i would be very nice if every 2nd, 3rd and 5th... number would not be relatively prime to n

think about that and it will give you a pen and paper answer

ans：510510

Totient permutation

Problem 70

Euler's Totient function, φ(n) [sometimes called the phi function], is used to determine the number of positive numbers less than or equal to?n?which are relatively prime to?n. For example, as 1, 2, 4, 5, 7, and 8, are all less than nine and relatively prime to nine, φ(9)=6.
The number 1 is considered to be relatively prime to every positive number, so φ(1)=1.

Interestingly, φ(87109)=79180, and it can be seen that 87109 is a permutation of 79180.

Find the value of?n, 1 <?n?< 10^7, for which φ(n) is a permutation of?n?and the ratio?n/φ(n) produces a minimum.

φ(87109)=79180? 79180恰好是87109的后續(xù)全排列。

找到φ(n)是n的全排列的n（1 <?n?< 10^7） 并且比值n/φ(n)是最小值。

69的基礎(chǔ)加上排序函數(shù)即可..

ans：8319823

本期除了歐拉函數(shù)外基本是水題.

（ps：歐拉計(jì)劃的評(píng)論區(qū)只有在解決題目后才能瀏覽，里面有各種大佬的思路和討論）

有緣更新后續(xù).