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

觀前聲明：? ??

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

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

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

4. 語言是c++，用的VS平臺

Square root convergents

Problem 57

It is possible to show that the Square root of two can be expressed as an infinite continued fraction.

By expanding this for the first four iterations, we get:

The next three expansions are?99/70,?239/169, and?577/408, but the eighth expansion,?1393/985, is the first example where the number of digits in the numerator exceeds the number of digits in the denominator.

In the first one-thousand expansions, how many fractions contain a numerator with more digits than the denominator?

根號2的連分數(shù)展開如上（連分數(shù)的概念以后的題有機會細說.對這道題只要當作數(shù)列然后找規(guī)律就能解決）

1，3/2，7/5，17/12...

問前1000項內(nèi)有多少項是分子的位數(shù)大于分母的？

如果純當成找規(guī)律的數(shù)列（事實上我也是這么做的），不難發(fā)現(xiàn)如果上一項是x/y，下一項便是(x+2y)/(x+y)? 那么只要根據(jù)這個規(guī)律分開寫出前1000項的分子分母即可.

對于c++而言唯一不便的地方就只有項數(shù)大了之后爆了需要用大整數(shù)加法而已.

大整數(shù)加法已經(jīng)提及多次不再詳述（詳見13題）

我這里使用fracde[n][]表示第n項的分母（數(shù)組形式），fracnu[n][]表示第n項的分子

其他就是遞歸使用大整數(shù)加法.（getfraction函數(shù)）

不展開細究背后的連分數(shù)的話，這題也就是個水題了；但因為之后會遇到?所以我就不細說了.

ans：153

Spiral primes

Problem 58

Starting with 1 and spiralling anticlockwise in the following way, a Square spiral with side length 7 is formed.

37 36 35 34 33 32 31

38 17 16 15 14 13 30

39 18? ?5? ?4? ?3 12?29

40 19? ?6? ?1? ?2?11 28

41 20? ?7? ?8? ?9 10 27

42 21 22 23 24 25 26

43 44 45 46 47 48 49

It is interesting to note that the odd Squares lie along the bottom right diagonal, but what is more interesting is that 8 out of the 13 numbers lying along both diagonals are prime; that is, a ratio of 8/13 ≈ 62%.

If one complete new layer is wrapped around the spiral above, a Square spiral with side length 9 will be formed. If this process is continued, what is the side length of the Square spiral for which the ratio of primes along both diagonals first falls below 10%?

以自然數(shù)旋轉(zhuǎn)生成的7×7矩陣中，在對角線的13個數(shù)中，有8個質(zhì)數(shù)，比例是8/13≈62%

那么如果這個矩陣不斷生成下去，到邊長為多少時這個比例會首次降至10%以下？

水題.

邊長為n的螺旋正方形對角線有2n-1個數(shù)字，所以只要檢驗3,5,...,n邊框上的3個數(shù)字是否為素數(shù)，再加起來最后除以2n-1就能獲得比率。

顯見邊為n的正方形的3個帶檢驗數(shù)（x1,x2,x3）為：

x1 = n * n - n + 1, x2 = x1 - n + 1, x3 = x2 - n + 1;

質(zhì)數(shù)檢驗用最樸實的因子檢驗（o(n^1/2)）即可??

為了方便，可在全局設一個數(shù)組記錄邊為n時該邊的質(zhì)數(shù)個數(shù)，Square[n]=0或1或2或3，上限設置的大一點就不怕跑不到.

ans：26241

XOR decryption

Problem 59

Each character on a computer is assigned a unique code and the preferred standard is ASCII (American Standard Code for Information Interchange). For example, uppercase A = 65, asterisk (*) = 42, and lowercase k = 107.

A modern encryption method is to take a text file, convert the bytes to ASCII, then XOR each byte with a given value, taken from a secret key. The advantage with the XOR function is that using the same encryption key on the cipher text, restores the plain text; for example, 65 XOR 42 = 107, then 107 XOR 42 = 65.

For unbreakable encryption, the key is the same length as the plain text message, and the key is made up of random bytes. The user would keep the encrypted message and the encryption key in different locations, and without both "halves", it is impossible to decrypt the message.

Unfortunately, this method is impractical for most users, so the modified method is to use a password as a key. If the password is shorter than the message, which is likely, the key is repeated cyclically throughout the message. The balance for this method is using a sufficiently long password key for security, but short enough to be memorable.

Your task has been made easy, as the encryption key consists of three lower case characters. Using?p059_cipher.txt?(right click and 'Save Link/Target As...'), a file containing the encrypted ASCII codes, and the knowledge that the plain text must contain common English words, decrypt the message and find the sum of the ASCII values in the original text.

?p059_cipher.txt：https://projecteuler.net/project/resources/p059_cipher.txt

這是一道密碼學相關(guān)的題，它是目前我在pe中見過的最浪漫最酷的題。

雖然這里只是簡單的用異或運算進行加密

姑且說下異或加密規(guī)則：

異或加密就是將明文字符對應的ascii碼值與密鑰字符對應的ascii碼值相異或把得到的ascii碼值對應的字符作為密文，從而實現(xiàn)加密。對于明文長度長于密鑰的情況，則循環(huán)使用密鑰對明文進行加密，如明文為I am happy（包括空格10個字符），密鑰為key，加密時應將明文與keykeykeyk一一對應進行異或，需注意這里空格也有對應的ascii碼，加密的時候如果是對整個明文直接進行加密，空格也會被加密。

題設給了我們一個已經(jīng)被加密的文件并告知密鑰為3個字符，文件里是加密后的ascii碼值，我們的任務就是破解加密的文件，還原文本后，將原文本所有的ascii碼值相加得到答案。

關(guān)于這題，有個很簡單的思路，這也可以作為以后頻率分析的啟蒙。

有1455個數(shù)，跑幾遍后可以獲得以下信息：最大值為95。

密鑰為3個字符，將密文的第0 3 6 9 ..劃為一組，第1 4 7 10...劃為一組，第2 5 8 11...劃為一組，分別找到每組中出現(xiàn)次數(shù)最高的數(shù)字，將這個數(shù)字和空格的ascii碼32相異或，得到密鑰。

關(guān)于頻率分析，有位up已經(jīng)針對此題寫了篇不錯的專欄? (@穆罕默德-李)

https://www.bilibili.com/read/cv7078915有比我更為詳盡的分析 還引經(jīng)據(jù)典的擴展了背景，有興趣者不妨去看看。

我首先將這些數(shù)字放在數(shù)組A[]中，然后先分組 跑一遍看3組中哪3個數(shù)字出現(xiàn)最多：

這樣跑一遍之后分別得到3組中頻率最高的為：69 88 80

與32（空格的ascii碼）異或后分別得到101，120，112；（對應exp）

再將下述放入上面的主函數(shù)中便可直接算原文本的ascii碼

int sec1 = (max1i ^ 32), sec2 = (max2i ^ 32), sec3 = (max3i ^ 32), sum = 0;

for (i = 0; i < 485; i++)

{

sum += (A1[i] ^ sec1);

sum += (A2[i] ^ sec2);

sum += (A3[i] ^ sec3);

}

cout << sum;

但...都做到這個地步了怎么可能不輸出原文本是啥

轉(zhuǎn)碼也很簡單 異或回去后直接char()那個數(shù)值就能變?yōu)樽址?，逐個輸出即可

轉(zhuǎn)碼代碼：

char s[1455];

for (i = 0; i < 485; i++)

{

A1[i] = (A1[i] ^ sec1);

A2[i] = (A2[i] ^ sec2);

A3[i] = (A3[i] ^ sec3);

}

? ? ? ? for (i = 0,j1=0,j2=0,j3=0; i < 1455; i++)

{

if (i % 3 == 0)s[i] = char(A1[j1++]);

if ((i - 1) % 3 == 0)s[i] = char(A2[j2++]);

if ((i + 1) % 3 == 0)s[i] = char(A3[j3++]);

}

for (i = 0; i < 1455; i++)

cout << s[i];

原文：

An extract taken from the introduction of one of Euler's most celebrated papers, "De summis serierum reciprocarum" [On the sums of series of reciprocals]: I have recently found, quite unexpectedly, an elegant expression for the entire sum of this series 1 + 1/4 + 1/9 + 1/16 + etc., which depends on the quadrature of the circle, so that if the true sum of this series is obtained, from it at once the quadrature of the circle follows. Namely, I have found that the sum of this series is a sixth part of the Square of the perimeter of the circle whose diameter is 1; or by putting the sum of this series equal to s, it has the ratio sqrt(6) multiplied by s to 1 of the perimeter to the diameter. I will soon show that the sum of this series to be approximately 1.644934066842264364; and from multiplying this number by six, and then taking the Square root, the number 3.141592653589793238 is indeed produced, which expresses the perimeter of a circle whose diameter is 1. Following again the same steps by which I had arrived at this sum, I have discovered that the sum of the series 1 + 1/16 + 1/81 + 1/256 + 1/625 + etc. also depends on the quadrature of the circle. Namely, the sum of this multiplied by 90 gives the biquadrate (fourth power) of the circumference of the perimeter of a circle whose diameter is 1. And by similar reasoning I have likewise been able to determine the sums of the subsequent series in which the exponents are even numbers.

這是歐拉在解決平方無窮級數(shù)和的問題∑1/(k^2)=（π^2/）6的一篇論文中的選段。

（關(guān)于這個問題自行搜索.?證明會用到泰勒展開 根的分析等 或直接去閱讀歐拉本人的《無窮分析引論》也可）

在破解出原文的那刻，以我粗淺且稀缺的詞匯，我只能說，這道題簡直浪漫到死好嗎！

ans：129448

Prime pair sets

Problem 60

The primes 3, 7, 109, and 673, are quite remarkable. By taking any two primes and concatenating them in any order the result will always be prime. For example, taking 7 and 109, both 7109 and 1097 are prime. The sum of these four primes, 792, represents the lowest sum for a set of four primes with this property.

Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime.

3，7，109，673這個4質(zhì)數(shù)集合具有非凡的性質(zhì)，不論如何組合它們，37，73，7109，1097...等等 都會得到一個新的質(zhì)數(shù)，它們的和792代表了具有這個性質(zhì)的且和最小的4素數(shù)集合。找到具有這樣的性質(zhì)最小的5素數(shù)集合，并求出它們的和。

事實上 我第一個思路就是完完全全的暴搜，先跑出一定范圍的質(zhì)數(shù)保證5個素數(shù)都在其中（實際上這個和很小 才5位數(shù)），然后兩兩相接檢驗（數(shù)化數(shù)組相接，數(shù)組化數(shù)檢驗）

然后寫了個非常丑還要跑很久的代碼（好像跑了幾小時跑出來了）：

getprime函數(shù)中Bprime獲得一個順序排列的全是素數(shù)的數(shù)組（埃氏篩）；

check函數(shù)檢驗2個素數(shù)是否符合性質(zhì)

check5n函數(shù)利用check函數(shù)檢驗5個

然后是不忍直視的主函數(shù)...用a b c d e代表質(zhì)數(shù)序號，暴搜找...

關(guān)于優(yōu)化部分，可以直接在素數(shù)中分組，比如把這些素數(shù)分成mod3余1和余2的2組，然后在2組內(nèi)分別找（因為任取2組中各一個相加都會是3的倍數(shù)，所以首尾相接必定不是素數(shù)）：

這樣會快一點

void getmod12(void)

{

for (int i = 0, j1 = 0, j2 = 0; Bprime[i] != 0; i++)

if (Bprime[i] % 3 == 1)B1prime[j1++] = Bprime[i];

else B2prime[j2++] = Bprime[i];

}

別的優(yōu)化還有類似計算一次記錄一次，比如abcde不符合，則之后不會再判斷出現(xiàn)ab,ac,ad,ae,bc,bd,be,cd,ce的情況等等.

但我既然都跑完了 就懶得優(yōu)化了...優(yōu)化部分自己寫吧。

質(zhì)數(shù)分別為 13，5197，5701，6733，8389

ans：26033

（實際上除了60是20%的難度，其余3道都是5%..）

后續(xù)隨緣更新.