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

观前声明：            

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

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

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

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

前排：74，75是偏水的散题，76，77，78是关于整数划分的系列题.因为单独1期出2题太水了 所幸放一起...

76，77，78的整数划分中出现的动态规划思想是非常有意思，且值得思考如何实现的算法

所以本期会稍微啰嗦一点.

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?

数字 145 有一个著名的性质：其所有位上数字的阶乘和等于它本身。

169 不像 145 那么有名，但是 169 可以产生能够连接回它自己的数字链。

不难证明从每个数字出发后都将陷入循环（例子见上）。从 69 开始可以产生一条有 5 个不重复元素的链。

并且，以一百万以下的数开始，能够产生的最长的不重复链包含 60 个项。

一共有多少条以一百万以下的数开始的链包含 60 个不重复项？

感觉好像之前做过类似的？

要确认一个起始数字的链长，需要不断获得其各位数字上的阶乘之和并储存在数组之中，每次获得新的数字需要检查这个数字受否重复。（实际上set库能很容易实现. 在外部放一个数组储存每个数字的下一位数字都是不错的优化方法...但是 这与我一个头铁选手又有什么关系）

获得各位数字阶乘之和就是数化数组没啥难度，提前用一个数组存好1~9的阶乘就行

我的判断链长函数写的非常没有效率 但最长不过60个数字，所以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?

周长为12cm的整数边正三角形只有1种：(3,4,5)

周长为24,30,36,40,48的整数边正三角形也只有1种；

但周长为120时能形成3种整数边正三角形： (30,40,50), (20,48,52), (24,45,51)

周长L<=1500000时，有多少的L仅能形成一种整数边正三角形。

第九题中有类似关于生成勾股数公式的结论：

如果勾股数a,b,c的最大公因数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互质，m,n一奇一偶，而所有的勾股数可以由此派生   a=t*2mn，b=t*(m^2-n^2)，c=t*(m^2+n^2)

（a,b可互换，在题设中a<b 所以a为2mn与m^2-n^2中的较小者）

让m从1跑到1224，n从1跑到m-1

若生成的a,b,c最大公因数为1，则记录储存对应的周长L=a+b+c的lenth[L]+1，及其倍数lenth[t*L]+1(t>1)即可

74，75的难度比是15% 25%. 是不是感觉也没那么难？确实很多时候这个难度是假的(?)

下三道是关于整数规划的，颇有点像，或者说就是 高等代数里对称多项式的字典排序..

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有多少种呢？

先说说整数划分的动态规划思想：(部分文字摘自百度百科)

整数划分，是指把一个正整数n写成如下形式：n=m1+m2+...+mn; （其中mi为正整数，并且1 <= mi <= n），则{m1,m2,...,mn}为n的一个划分。

如果{m1,m2,...,mn}中的最大值不超过m，即max(m1,m2,...,mn)<=m，则称它属于n的一个m划分。这里我们记n的m划分的个数为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)当n=1时，不论m的值为多少（m>0)，只有一种划分即{1};

(2) 当m=1时，不论n的值为多少，只有一种划分即n个1，{1,1,1,...,1};

(3) 当n=m时，根据划分中是否包含n，可以分为两种情况：

(a). 划分中包含n的情况，只有一个即{n}；

(b). 划分中不包含n的情况，这时划分中最大的数字也一定比n小，即n的所有(n-1)划分。

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

(4) 当n<m时，由于划分中不可能出现负数，因此就相当于f(n,n);

(5) 但n>m时，根据划分中是否包含最大值m，可以分为两种情况：

(a). 划分中包含m的情况，即{m, {x1,x2,...xi}}, 其中{x1,x2,... xi} 的和为n-m，可能再次出现m，因此是（n-m）的m划分，因此这种划分

个数为f(n-m, m);

(b). 划分中不包含m的情况，则划分中所有值都比m小，即n的(m-1)划分，个数为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)

而对于此题，只需考虑最后一种f(n,m)=f(n-m,m)+f(n,m-1)

根据最后一种情况来构造动态规划，我们令dop[n]来储存最终结果的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的循环中，dop[2]+=dop[1],dop[4]+=dop[3]   

此时只能储存f(n,1)的情况，所以f(4,4)先加上f(3,1)   f(2,2)加上了f(1,1)

第二轮i=2的循环中，dop[4]+=dop[2]   dop[2]+=dop[0]

i=2时跑完dop[2]后 dop[2]已经表示f(2,2)：f(2,2)=f(0,0)+f(1,1)。这一步dop[2]+=dop[0]对应f(2,2)+=f(0,0)     而dop[4]+=dop[2]对应f(4,4)+=f(2,2)

第三轮i=3的循环中，dop[4]+=dop[1]   在第一轮后dop[1]就已经表示f(1,1)，对应f(4,4)+=f(1,1)

第四轮i=4的循环中，dop[4]+=dop[0]   对应f(4,4)+=f(0,0)

第五轮开始时dop[4]已经储存f(4,4)最终值：f(4,4)=f(0,0)+f(1,1)+f(2,2)+f(3,1)

（第i轮开始时前i-1个数的最终dop值已储存）

可以理解为：第i轮时每个dop[]仅能储存最大数为i的情况。

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

针对这道题如果不用整数划分，要怎么做呢

（毕竟规模也不大，我开始时也并没有想到要如何使用整数划分，而是直接递归暴搜）

大概递归思路是，如果要考虑x1+x2+..+xm=S的所有情况

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

当然这个算法非常的不高效，需要1min左右才能做到整数划分1ms跑出来的事

之所以在这里提一下是因为77当时莫得用动态规划而是用了这个算法加一些修改....

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如果用素数的加法来表示可以有5种表示方法，那么第一个可以用超过5000种数字表示的数是什么？

这题为了偷懒，我直接在76第二个算法代码的思路上加了个素数表和素数判断。

实际上，这题也能用整数划分中的动态规划做，只是多需要考虑带有素数情况的约束而已

有兴趣的同学不妨自己想一下怎么实现。

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个硬币有7种分隔方式（见上），记p(5)=7

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

实际上这就是求f(n,n) 直接搬76题的代码即可

但因为这道题数据规模较大，辣鸡的c++会溢出，但我们只需要求能够整除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;

           }

主函数中找到第一个dop[n]等于0的n即可。

ans：55374

总算写完了，其实做到这题时我才了解了整数划分，希望大家也有所收获.

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

放张图当封面.