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

观前声明：       

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

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

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

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

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）

问题与pe18：Maximum path sum I 同出一辙，只是数据不一样了而已

解法在pe18题已经给出. 经典动态规划题。

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?

在一个3-gon ring中填上数字1~6，使得每条线的和相等。若这个和为9，从最小的外圈开始以顺时针将3条线逐一列出 可以形成 4,3,2; 6,2,1; 5,1,3  ：

若以432621513代表其得到的数字，那么3-gon ring能得到的最大数字是432621513

考虑5-gon ring 填上数字1~10，它能得到16或17位数字（若数字10作为中间位则能得到17位数字，不然得到的是16位），那么5-gon ring能得到的最大的16位数字是多少

这道题是能够手算的，因为要得到16位，即10在外圈，又要满足最大情况，只要考虑外圈都是较大的数字如6 7 8 9 10，内圈都是较小的数字1 2 3 4 5

并注意到6+7+8+9+10+2(1+2+3+4+5)=70  即每条线和为14

稍加观察不难发现653   725  842   914   1031  恰好能满足

（考虑的时候要按6 10 9 8 7的顺序考虑并且时刻注意满足最大数）

排列一下就是6531031914842725。

但这题也能暴搜出来，我使用了看着最丑的for的写法，在一个长度为10数组里，

写了9个for(A[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.

欧拉函数φ(n)表示：对正整数n，小于或等于n的数中与n互质的数的数目。

比如6，这样的数有1，5，所以φ(6)=2   6/φ(6)=3

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

表面上来看  利用同余定理验证是否互质来计算欧拉函数再跑个1000000的暴搜也不是不行，大概10min

（同余定理的一个结论：a%b=(b%(a%b))（a>=b） 证明自行翻阅数论吧）

代码可写成：

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;

}

但这里我们采用更聪明的写法，利用欧拉函数本身的性质直接得到一个欧拉函数值得表，储存在phi[]数组中。

欧拉函数的3个性质：

性质① m是素数时，有φ(m)=m-1

性质② 当m、n互素时，φ(m*n)=φ(m)*φ(n)

性质③ 对一切正整数n，有φ(p^n)=[p^(n-1)]*(p-1) （p为质数）  

（证明请自己尝试或查阅资料）

利用筛子先跑一个质数表储存在数组prime[]中(prime[i]=0代表i是质数，另外再用一个bprime[]数组按顺序储存质数)，对于phi[i]，如果i是个质数，那么phi[i]=i-1，如果i是个合数，那么小于i的所有质数的倍数i * bprime[j]满足phi[i * bprime[j]] = phi[i] *  phi[bprime[j]]（性质2）

并且值得注意的是如果bprime[j]是i的质因子，那么：

phi[i * bprime[j]] = phi[i] * bprime[j]（即若m,n是正整数,m|n,则φ(mn)=mφ(n)）

（事实上比较2者定义：phi(n) 是 1 到 n 中与n 互素的数的个数.phi(mn) 是 1 到 mn 中与 mn 互素的数的个数即可证明）

关于32行的break 是为了避免重复运算，举个例子：

i = 8，j=1，bprime[j] = 2，如果不跳出循环，prime[j+1]=3，8*3=2*4*3=2*12，在i=12时会计算。因为欧拉筛法的原理便是通过最小素因子来消除。

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

评论区也有不少手算的大佬. 摘一个大佬的思路：

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的后续全排列。

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

69的基础加上排序函数即可..

ans：8319823

本期除了欧拉函数外基本是水题.

（ps：欧拉计划的评论区只有在解决题目后才能浏览，里面有各种大佬的思路和讨论）

有缘更新后续.