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

观前声明：               

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

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

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

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

前排：本期头铁.

Right triangles with integer coordinates

Problem 91

The points P (x1, y1) and Q (x2, y2) are plotted at integer co-ordinates and are joined to the origin, O(0,0), to form ΔOPQ.

There are exactly fourteen triangles containing a right angle that can be formed when each co-ordinate lies between 0 and 2 inclusive; that is,
0 ≤ x1, y1, x2, y2 ≤ 2.

Given that 0 ≤ x1, y1, x2, y2 ≤ 50, how many right triangles can be formed?

点P,Q位于整数点坐标上，并且与原点 O(0,0) 相连接形成三角形 ΔOPQ。

当横纵坐标都位于 0 到 2 之间时（包括 0 和 2），一共可以形成 14 个直角三角形。（见上）

那么当横纵坐标都位于0~50时，能形成多少直角三角形？

这题.这题是想了半天递推没有一个暴搜快...

4个for遍历所有的x1,x2,y1,y2如果是直角三角形那么计数...

过了之后又懒得想别的方法了

代码实现没有什么难度就不放了.

ans：14234

square digit chains

Problem 92

A number chain is created by continuously adding the square of the digits in a number to form a new number until it has been seen before.

For example,

44 → 32 → 13 → 10 → 1 → 1
85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89

Therefore any chain that arrives at 1 or 89 will become stuck in an endless loop. What is most amazing is that EVERY starting number will eventually arrive at 1 or 89.

How many starting numbers below ten million will arrive at 89?

通过将一个数各位的平方不断相加，直到遇到已经出现过的数字，可以形成一个数字链。

44最终可以得到1，85最终可以得到89.

因此任何到达 1 或 89 的数字链都会陷入无限循环。

神奇的是，以任何数字开始，最终都会到达 1 或 89。

以一千万以下的数字 n 开始，有多少个 n 会到达 89？

这个确实很奇妙，不知道数论有没有证明。

不过单纯当成已知条件来解题的话，也没什么难度

在外部放一个数组储存每个数字最后回到的是89还是1

边搜边记录即可.

比如从44开始，在搜44的过程中将44的“路径”上的数记录：32 13 10

44到达1后数组标记Nreturn[44]=1,Nreturn[32]=1,Nreturn[13]=1,Nreturn[10]=1,

并且在跑的过程中先判断各位数字平方和是否已被标记

这样在总的循环能节省不少时间。

思路对应arrive函数.

ans：8581146

Arithmetic expressions

Problem 93

By using each of the digits from the set, {1, 2, 3, 4}, exactly once, and making use of the four arithmetic operations (+, −, *, /) and brackets/parentheses, it is possible to form different positive integer targets.

For example,

Note that concatenations of the digits, like 12 + 34, are not allowed.

Using the set, {1, 2, 3, 4}, it is possible to obtain thirty-one different target numbers of which 36 is the maximum, and each of the numbers 1 to 28 can be obtained before encountering the first non-expressible number.

Find the set of four distinct digits, a < b < c < d, for which the longest set of consecutive positive integers, 1 to n, can be obtained, giving your answer as a string: abcd.

通过使用集合 {1, 2, 3, 4} 中每个数字一次（用且只用一次），以及四种算术运算和括号，可以得到不同的正整数。

但是将相连接是不允许的，如 12 + 34。
使用集合 {1, 2, 3, 4} 可以得到 31 个目标数，其中最大的是 36。而且 1 到 28 中的每个数字都可以被表示，但是 29 不能被表示。
找出四个不同1位数的集合，a < b < c < d，能够形成最长的 1 到 n 的连续正整数集合。以 abcd 的形式给出你的答案。

规模不大  直接BF ...

需要注意要写出所有可能的加减乘除组合

令cal(a,b,x)代表进行a b关于x的二元运算，x=0,1,2,3分别表示+ - * /

a b c d在不考虑运算是否相同时的位置安排共有5种 

如果用(a,b)表示a b先进行括号内的某个运算：

((a,b),(c,d))

(((a,b),c),d)

((a,(b,c)),d)

(a,((b,c),d))

(a,(b,(c,d)))

把(a,b)看成cal(a,b,xi)即可，xi要取遍0~3，如果能够得到整数，那么就记录。

这里记录我使用了c++的set库，基于红黑树帮我记录储存

对应代码：

开头要包含set库

#include<set>

然后建一个树：

set<int> tree;

26行的   tree.insert(tmp); 语句就是把tmp值插入到树中（详细知识请先学二叉树等.）

红黑树会自动对数据进行从小到大的排序，并且如果有重复的数据只会保留一个。

之后就是在主函数中用4个for循环代表a b c d

使用next_permutation函数得到a b c d的全排列

每一个顺序再用3个循环遍历x1 x2 x3的取值（所有可能的+ - * /）

对每个abcd组合记录替换abcd值和对应的能得到的最多的连续整数

由此得到最大值：

（关于set库的用法 详细还是看书或者百度比较好. 类似的封装库还有list map vector）

ans：1258

Almost equilateral triangles

Problem 94

It is easily proved that no equilateral triangle exists with integral length sides and integral area. However, the almost equilateral triangle 5-5-6 has an area of 12 square units.

We shall define an almost equilateral triangle to be a triangle for which two sides are equal and the third differs by no more than one unit.

Find the sum of the perimeters of all almost equilateral triangles with integral side lengths and area and whose perimeters do not exceed one billion (1,000,000,000).

容易证明不存在具有整数边长和整数面积的等边三角形。但是 5 5 6 这个近似等边三角形具有整数面积 12。
将近似等边三角形定义为有两边相等，并且第三边与其他两边相差不超过 1 的三角形。
对于周长不超过 10 亿的三角形中，找出边长和面积都为整数的近似等边三角形的周长和。

..

先别忙着暴搜.

写成代数的形式看看.

第一种情况：先令三边为m,m,m+1

根据海伦公式，面积s=1/4*(m+1)*sqrt((3*m+1)*(m-1))

可知m必须是奇数，令m=2k+1，得s=(k+1)*sqrt((3k+2)*k)

考察k和3k+2  易证2者不存在大于2的公因数：

不然k=c1*d,3k+2=c2*d=3c1*d+2

(c2-3c1)*d=2，与d>2矛盾

若k是奇数：

则k与3k+2互质显然，

所以k*(3k+2)是完全平方数可推出k,3k+2均是完全平方数

这时令k=x^2，函数中检验3x^2+2是否为完全平方数即可。

若k是偶数：

令k=2y

s=2(2y+1)sqrt(y(3y+1))

y与3y+1互质显然

所以y和3y+1必须是完全平方数

令y=x^2，考察3y+1是否完全平方数即可。

2类情况的x搜索范围分别为：x<12910且x是奇数；x<9129；（由周长上限得到）

第二种情况：令三边为m,m,m-1

类似上述分析：

s=1/4*(m-1)*sqrt((3*m-1)*(m+1))，可知m必须是奇数，令m=2k-1，得s=k*sqrt((3k-2)*k)

k是奇数：令k=x^2，考察3k-2是否完全平方数即可。（x<12910且x是奇数）

k是偶数：令k=2y，y=x^2，考察3y-1是否完全平方数即可。（根据边长范围得：x<9129）

虽然这个思路能快速搜索出答案。

不过pe评论区有个大佬写了个我至今没懂的递推：

int m[MAxi] = { -1, 1 };

m[i] = (i%2==0)?(m[i-1]+m[i-2]):(2*m[i-1]+m[i-2]);

        a += 4*m[i]*m[i-1];

        b = (i%2==0) ? (a+1) : (a-1);

sum+=a+a+b

获得这个表：

去掉第一个和二个 因为不是三角形

518408352-6即为答案

如果有懂得快来评论区教教我.

ans：518408346

Amicable chains

Problem 95

The proper divisors of a number are all the divisors excluding the number itself. For example, the proper divisors of 28 are 1, 2, 4, 7, and 14. As the sum of these divisors is equal to 28, we call it a perfect number.

Interestingly the sum of the proper divisors of 220 is 284 and the sum of the proper divisors of 284 is 220, forming a chain of two numbers. For this reason, 220 and 284 are called an amicable pair.

Perhaps less well known are longer chains. For example, starting with 12496, we form a chain of five numbers:

12496 → 14288 → 15472 → 14536 → 14264 (→ 12496 → ...)

Since this chain returns to its starting point, it is called an amicable chain.

Find the smallest member of the longest amicable chain with no element exceeding one million.

一个数的真因子是指除了其本身以外的所有因子。例如，28 的真因子是 1,2,4,7 和 14。因为这些因子之和等于 28，称 28 为一个完美数。

有趣的是，220 的真因子之和是 284，而 284 的真因子之和是 220，形成了一个两个元素的链。因此 220 和 284 被称为一个亲和对。

可能更长的链就不那么为人所知了，例如，从 12496 开始，我们可以得到一个五个元素的链：12496 → 14288 → 15472 → 14536 → 14264 (→ 12496 → ...)

因为这条链最后回到了开始的数，它被称为一条亲和链。

对于元素都不超过一百万的亲和链，找出最长的亲和链中最小的元素。

类似92题的动态存储 不过这次要考虑最后是否能得到自身.

所以只能先跑一个储存真因子和的数组nextn[]

方法类似埃氏筛子，n从1开始，n的倍数k*n肯定包含了n这个因子

所以跑到n时，遍历所有的k*n，令nextn[k*n]+n

然后写一个考察n生成的亲和链长的函数（n不能生成亲和链则链长为0，同时如果考察的过程中nk超过了上限1000000由题意不须计算，也令链长为0）

检验n的时候可以用93题用过的set库，每次将nextn[n]插入树中，如果有重复的数字且重复的数字是开始的n则生成了一条亲和链，不然则链长为0

因为红黑树不会插入已有的数字，

所以在

st.insert(nk);

这个语句之后检验树的元素有没有变化即可。

然后主函数动态更替找到的最大链长即可.

（注意39行  每次找之前先把树清空.）

别的思路.

把这些数看作图，n指向nextn[n]然后taejan算法或者floyd判定链长.

但俺懒得实现..

ans：14316

本次难度比是25% 5% 35% 35% 30% 其实也没什么特别难想到的地方.头铁都能过.

剩一期就要完结撒花了吗...

搞个图做封面.