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

觀前聲明：? ? ? ? ? ??

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

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

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

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

前排：74，75是偏水的散題，76，77，78是關(guān)于整數(shù)劃分的系列題.因?yàn)閱为?dú)1期出2題太水了 所幸放一起...

76，77，78的整數(shù)劃分中出現(xiàn)的動(dòng)態(tài)規(guī)劃思想是非常有意思，且值得思考如何實(shí)現(xiàn)的算法

所以本期會(huì)稍微啰嗦一點(diǎn).

Digit factorial chains

Problem 74

The number 145 is well known for the property that the sum of the factorial of its digits is equal to 145:

1! + 4! + 5! = 1 + 24 + 120 = 145

Perhaps less well known is 169, in that it produces the longest chain of numbers that link back to 169; it turns out that there are only three such loops that exist:

169 → 363601 → 1454 → 169
871 → 45361 → 871
872 → 45362 → 872

It is not difficult to prove that EVERY starting number will eventually get stuck in a loop. For example,

69 → 363600 → 1454 → 169 → 363601 (→ 1454)
78 → 45360 → 871 → 45361 (→ 871)
540 → 145 (→ 145)

Starting with 69 produces a chain of five non-repeating terms, but the longest non-repeating chain with a starting number below one million is sixty terms.

How many chains, with a starting number below one million, contain exactly sixty non-repeating terms?

數(shù)字 145 有一個(gè)著名的性質(zhì)：其所有位上數(shù)字的階乘和等于它本身。

169 不像 145 那么有名，但是 169 可以產(chǎn)生能夠連接回它自己的數(shù)字鏈。

不難證明從每個(gè)數(shù)字出發(fā)后都將陷入循環(huán)（例子見上）。從 69 開始可以產(chǎn)生一條有 5 個(gè)不重復(fù)元素的鏈。

并且，以一百萬(wàn)以下的數(shù)開始，能夠產(chǎn)生的最長(zhǎng)的不重復(fù)鏈包含 60 個(gè)項(xiàng)。

一共有多少條以一百萬(wàn)以下的數(shù)開始的鏈包含 60 個(gè)不重復(fù)項(xiàng)？

感覺好像之前做過類似的？

要確認(rèn)一個(gè)起始數(shù)字的鏈長(zhǎng)，需要不斷獲得其各位數(shù)字上的階乘之和并儲(chǔ)存在數(shù)組之中，每次獲得新的數(shù)字需要檢查這個(gè)數(shù)字受否重復(fù)。（實(shí)際上set庫(kù)能很容易實(shí)現(xiàn). 在外部放一個(gè)數(shù)組儲(chǔ)存每個(gè)數(shù)字的下一位數(shù)字都是不錯(cuò)的優(yōu)化方法...但是 這與我一個(gè)頭鐵選手又有什么關(guān)系）

獲得各位數(shù)字階乘之和就是數(shù)化數(shù)組沒啥難度，提前用一個(gè)數(shù)組存好1~9的階乘就行

我的判斷鏈長(zhǎng)函數(shù)寫的非常沒有效率 但最長(zhǎng)不過60個(gè)數(shù)字，所以BF也不慢

ans：402

Singular integer right triangles

Problem 75

It turns out that 12 cm is the smallest length of wire that can be bent to form an integer sided right angle triangle in exactly one way, but there are many more examples.

12 cm: (3,4,5)
24 cm: (6,8,10)
30 cm: (5,12,13)
36 cm: (9,12,15)
40 cm: (8,15,17)
48 cm: (12,16,20)

In contrast, some lengths of wire, like 20 cm, cannot be bent to form an integer sided right angle triangle, and other lengths allow more than one solution to be found; for example, using 120 cm it is possible to form exactly three different integer sided right angle triangles.

120 cm: (30,40,50), (20,48,52), (24,45,51)

Given that L is the length of the wire, for how many values of L ≤ 1,500,000 can exactly one integer sided right angle triangle be formed?

周長(zhǎng)為12cm的整數(shù)邊正三角形只有1種：(3,4,5)

周長(zhǎng)為24,30,36,40,48的整數(shù)邊正三角形也只有1種；

但周長(zhǎng)為120時(shí)能形成3種整數(shù)邊正三角形：?(30,40,50), (20,48,52), (24,45,51)

周長(zhǎng)L<=1500000時(shí)，有多少的L僅能形成一種整數(shù)邊正三角形。

第九題中有類似關(guān)于生成勾股數(shù)公式的結(jié)論：

如果勾股數(shù)a,b,c的最大公因數(shù)GCD(a,b,c)=1 （Greatest Common Divisor） 那么則存在m,n， 使a=2mn，b=m^2-n^2，c=m^2+n^2，且m>n，m,n互質(zhì)，m,n一奇一偶，而所有的勾股數(shù)可以由此派生? ?a=t*2mn，b=t*(m^2-n^2)，c=t*(m^2+n^2)

（a,b可互換，在題設(shè)中a<b 所以a為2mn與m^2-n^2中的較小者）

讓m從1跑到1224，n從1跑到m-1

若生成的a,b,c最大公因數(shù)為1，則記錄儲(chǔ)存對(duì)應(yīng)的周長(zhǎng)L=a+b+c的lenth[L]+1，及其倍數(shù)lenth[t*L]+1(t>1)即可

74，75的難度比是15% 25%. 是不是感覺也沒那么難？確實(shí)很多時(shí)候這個(gè)難度是假的(?)

下三道是關(guān)于整數(shù)規(guī)劃的，頗有點(diǎn)像，或者說(shuō)就是 高等代數(shù)里對(duì)稱多項(xiàng)式的字典排序..

It is possible to write five as a sum in exactly six different ways:

4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

How many different ways can one hundred be written as a sum of at least two positive integers?

用加法得到5有6種方式（見上，注意不包括5+0），那么得到100有多少種呢？

先說(shuō)說(shuō)整數(shù)劃分的動(dòng)態(tài)規(guī)劃思想：(部分文字摘自百度百科)

整數(shù)劃分，是指把一個(gè)正整數(shù)n寫成如下形式：n=m1+m2+...+mn; （其中mi為正整數(shù)，并且1 <= mi <= n），則{m1,m2,...,mn}為n的一個(gè)劃分。

如果{m1,m2,...,mn}中的最大值不超過m，即max(m1,m2,...,mn)<=m，則稱它屬于n的一個(gè)m劃分。這里我們記n的m劃分的個(gè)數(shù)為f(n,m);

例如上述的n=5，f(5,4)=6，{4,1},{3,2},{3,1,1},{2,2,1},{2,1,1,1},{1,1,1,1,1};

考慮f(n,m)：

(1)當(dāng)n=1時(shí)，不論m的值為多少（m>0)，只有一種劃分即{1};

(2) 當(dāng)m=1時(shí)，不論n的值為多少，只有一種劃分即n個(gè)1，{1,1,1,...,1};

(3) 當(dāng)n=m時(shí)，根據(jù)劃分中是否包含n，可以分為兩種情況：

(a). 劃分中包含n的情況，只有一個(gè)即{n}；

(b). 劃分中不包含n的情況，這時(shí)劃分中最大的數(shù)字也一定比n小，即n的所有(n-1)劃分。

因此 f(n,n) =1 + f(n,n-1);

(4) 當(dāng)n<m時(shí)，由于劃分中不可能出現(xiàn)負(fù)數(shù)，因此就相當(dāng)于f(n,n);

(5) 但n>m時(shí)，根據(jù)劃分中是否包含最大值m，可以分為兩種情況：

(a). 劃分中包含m的情況，即{m, {x1,x2,...xi}}, 其中{x1,x2,... xi} 的和為n-m，可能再次出現(xiàn)m，因此是（n-m）的m劃分，因此這種劃分

個(gè)數(shù)為f(n-m, m);

(b). 劃分中不包含m的情況，則劃分中所有值都比m小，即n的(m-1)劃分，個(gè)數(shù)為f(n,m-1);

因此 f(n, m) = f(n-m, m)+f(n,m-1);

綜上，f(n, m)有4種可能的遞歸情況：

1; (n=1 or m=1)

f(n, n); (n<m)

1+ f(n, m-1); (n=m)

f(n-m,m)+f(n,m-1); (n>m)

而對(duì)于此題，只需考慮最后一種f(n,m)=f(n-m,m)+f(n,m-1)

根據(jù)最后一種情況來(lái)構(gòu)造動(dòng)態(tài)規(guī)劃，我們令dop[n]來(lái)儲(chǔ)存最終結(jié)果的f(n,n) dop[0]=f(0.0)=1

f(n,n)=1+f(n,n-1)=f(0,0)+f(1,n-1)+f(n,n-2)=f(0,0)+f(1,1)+f(2,n-2)+f(n,n-3)=.....

考慮這一過程得到下段代碼

int dop[105] = { 1 };

for (int i = 1; i <= 100; i++)

? ? ? for (int j = i; j <= 100; j++)

? ? ? ? ? ? ?dop[j] += dop[j - i];

為了方便解釋，我們不妨看:f(4,4)=f(0,0)+f(1,1)+f(2,2)+f(3,1)

第一輪i=1的循環(huán)中，dop[2]+=dop[1],dop[4]+=dop[3]? ?

此時(shí)只能儲(chǔ)存f(n,1)的情況，所以f(4,4)先加上f(3,1)? ?f(2,2)加上了f(1,1)

第二輪i=2的循環(huán)中，dop[4]+=dop[2]? ?dop[2]+=dop[0]

i=2時(shí)跑完dop[2]后 dop[2]已經(jīng)表示f(2,2)：f(2,2)=f(0,0)+f(1,1)。這一步dop[2]+=dop[0]對(duì)應(yīng)f(2,2)+=f(0,0)? ? ?而dop[4]+=dop[2]對(duì)應(yīng)f(4,4)+=f(2,2)

第三輪i=3的循環(huán)中，dop[4]+=dop[1]? ?在第一輪后dop[1]就已經(jīng)表示f(1,1)，對(duì)應(yīng)f(4,4)+=f(1,1)

第四輪i=4的循環(huán)中，dop[4]+=dop[0]? ?對(duì)應(yīng)f(4,4)+=f(0,0)

第五輪開始時(shí)dop[4]已經(jīng)儲(chǔ)存f(4,4)最終值：f(4,4)=f(0,0)+f(1,1)+f(2,2)+f(3,1)

（第i輪開始時(shí)前i-1個(gè)數(shù)的最終dop值已儲(chǔ)存）

可以理解為：第i輪時(shí)每個(gè)dop[]僅能儲(chǔ)存最大數(shù)為i的情況。

注意我們要求的是f(100,99) 所以最后要減1

針對(duì)這道題如果不用整數(shù)劃分，要怎么做呢

（畢竟規(guī)模也不大，我開始時(shí)也并沒有想到要如何使用整數(shù)劃分，而是直接遞歸暴搜）

大概遞歸思路是，如果要考慮x1+x2+..+xm=S的所有情況

那么只需取遍xm的值，考慮x1+x2+..+x(m-1)=S-xm的所有情況

當(dāng)然這個(gè)算法非常的不高效，需要1min左右才能做到整數(shù)劃分1ms跑出來(lái)的事

之所以在這里提一下是因?yàn)?7當(dāng)時(shí)莫得用動(dòng)態(tài)規(guī)劃而是用了這個(gè)算法加一些修改....

ans：190569291

Prime summations?

Problem 77

It is possible to write ten as the sum of primes in exactly five different ways:

7 + 3
5 + 5
5 + 3 + 2
3 + 3 + 2 + 2
2 + 2 + 2 + 2 + 2

What is the first value which can be written as the sum of primes in over five thousand different ways?

10如果用素?cái)?shù)的加法來(lái)表示可以有5種表示方法，那么第一個(gè)可以用超過5000種數(shù)字表示的數(shù)是什么？

這題為了偷懶，我直接在76第二個(gè)算法代碼的思路上加了個(gè)素?cái)?shù)表和素?cái)?shù)判斷。

實(shí)際上，這題也能用整數(shù)劃分中的動(dòng)態(tài)規(guī)劃做，只是多需要考慮帶有素?cái)?shù)情況的約束而已

有興趣的同學(xué)不妨自己想一下怎么實(shí)現(xiàn)。

ans：71

Coin partitions

Problem 78

Let p(n) represent the number of different ways in which?n?coins can be separated into piles. For example, five coins can be separated into piles in exactly seven different ways, so p(5)=7.

OOOOO

OOOO? O?

OOO? ?OO

OOO? ?O? ?O

OO? ?OO? ?O

OO? ?O? ?O? O

O? ?O? ?O? ?O? ?O

Find the least value of?n?for which p(n) is divisible by one million.

5個(gè)硬幣有7種分隔方式（見上），記p(5)=7

找到最小的n，使得p(n)能夠整除1000000。

實(shí)際上這就是求f(n,n) 直接搬76題的代碼即可

但因?yàn)檫@道題數(shù)據(jù)規(guī)模較大，辣雞的c++會(huì)溢出，但我們只需要求能夠整除1000000的p(n)

所以每次求出的dop[n]，令其余1000000即可。

dop[0] = 1;

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

? ? ? for (int j = i; j <= n; j++)

? ? ? ? ? ?{

? ? ? ? ? ? ? dop[j] += dop[j - i];

? ? ? ? ? ? ? dop[j] %= 1000000;

? ? ? ? ? ?}

主函數(shù)中找到第一個(gè)dop[n]等于0的n即可。

ans：55374

總算寫完了，其實(shí)做到這題時(shí)我才了解了整數(shù)劃分，希望大家也有所收獲.

78是第一道30%的題.不知大家感覺何如.

放張圖當(dāng)封面.