關于啥是Project Euler 詳見 https://projecteuler.net/about? ? ????

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

1. 這是個人興趣使然的對自己入坑pe的記錄，僅提供思路和部分代碼； 各個方面肯定都是有著優(yōu)化與提升空間的，甚至在許多大佬看來這應該是初學者的淺薄而未經剪枝的丑碼，如果能幫到有興趣的人自是最好，也歡迎能醍醐灌頂的深度討論。 ?

2. 大佬看到了笑笑就行，還請輕噴。

3. 帶著惡意，抬杠者...俺也噴不過您，也不能拿您咋樣...畢竟這只是我個人興趣使然的行為或者說是學習記錄分享。?（說是記錄，但因為是早先寫的所以其實是在各種意義上公開處刑和吐槽自己 并嘗試補救優(yōu)化）

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 的數字鏈都會陷入無限循環(huán)。

神奇的是，以任何數字開始，最終都會到達 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,

并且在跑的過程中先判斷各位數字平方和是否已被標記

這樣在總的循環(huán)能節(jié)省不少時間。

思路對應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 的連續(xù)正整數集合。以 abcd 的形式給出你的答案。

規(guī)模不大? 直接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循環(huán)代表a b c d

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

每一個順序再用3個循環(huán)遍歷x1 x2 x3的取值（所有可能的+ - * /）

對每個abcd組合記錄替換abcd值和對應的能得到的最多的連續(xù)整數

由此得到最大值：

（關于set庫的用法 詳細還是看書或者百度比較好. 類似的封裝庫還有l(wèi)ist 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評論區(qū)有個大佬寫了個我至今沒懂的遞推：

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即為答案

如果有懂得快來評論區(qū)教教我.

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題的動態(tài)存儲 不過這次要考慮最后是否能得到自身.

所以只能先跑一個儲存真因子和的數組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);

這個語句之后檢驗樹的元素有沒有變化即可。

然后主函數動態(tài)更替找到的最大鏈長即可.

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

別的思路.

把這些數看作圖，n指向nextn[n]然后taejan算法或者floyd判定鏈長.

但俺懶得實現..

ans：14316

本次難度比是25% 5% 35%?35% 30% 其實也沒什么特別難想到的地方.頭鐵都能過.

剩一期就要完結撒花了嗎...

搞個圖做封面.