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

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

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

2. 大佬看到了笑笑就行，還請(qǐng)輕噴。

3. 帶著惡意，抬杠者...俺也噴不過您，也不能拿您咋樣...畢竟這只是我個(gè)人興趣使然的行為或者說是學(xué)習(xí)記錄分享。?（說是記錄，但因?yàn)槭窃缦葘懙乃云鋵?shí)是在各種意義上公開處刑和吐槽自己 并嘗試補(bǔ)救優(yōu)化）

4. 語言是c++，用的VS平臺(tái)

100題啦.完結(jié)撒花，

o 還有600多道a 那沒事了.

再次介紹一下歐拉計(jì)劃. 這是個(gè)有著許多數(shù)學(xué)相關(guān)問題的網(wǎng)站，且每周都會(huì)更新一道題

大部分題都需要靈活的數(shù)學(xué)思維與編程技巧結(jié)合才能有效的解決.

我去做pe 僅是因?yàn)槟軌蛳硎芩伎寂c實(shí)現(xiàn)算法樂趣.甚至過程中還能被題目科普些新知識(shí)

如果您僅是來搜尋答案的話.那我覺得duck不必，解決的過程中的樂趣是無可替代的

pe的前100道題是新手教程題? 更完這期后以后可能咕了 也可能哪天閑著繼續(xù)更.看心情隨意更新

那么，開始最后的5道水題吧

Su Doku

Problem 96

Su Doku (Japanese meaning?number place) is the name given to a popular puzzle concept. Its origin is unclear, but credit must be attributed to Leonhard Euler who invented a similar, and much more difficult, puzzle idea called Latin squares. The objective of Su Doku puzzles, however, is to replace the blanks (or zeros) in a 9 by 9 grid in such that each row, column, and 3 by 3 box contains each of the digits 1 to 9. Below is an example of a typical starting puzzle grid and its solution grid.

A well constructed Su Doku puzzle has a unique solution and can be solved by logic, although it may be necessary to employ "guess and test" methods in order to eliminate options (there is much contested opinion over this). The complexity of the search determines the difficulty of the puzzle; the example above is considered?easy?because it can be solved by straight forward direct deduction.

The 6K text file,?sudoku.txt,contains fifty different Su Doku puzzles ranging in difficulty, but all with unique solutions (the first puzzle in the file is the example above).

By solving all fifty puzzles find the sum of the 3-digit numbers found in the top left corner of each solution grid; for example, 483 is the 3-digit number found in the top left corner of the solution grid above.

sudoku.txt：https://projecteuler.net/project/resources/p096_sudoku.txt

不會(huì)有人沒玩過數(shù)獨(dú)吧？？？？？

9×9網(wǎng)格內(nèi)每行每列每宮格（從左到右從上到下有9宮）的數(shù)字只能出現(xiàn)1次

例子的圖左非0數(shù)字是已給出數(shù)字，0是待填數(shù)字，圖右為數(shù)獨(dú)的解

數(shù)獨(dú)的魅力在于其是唯一解性的

上面這個(gè)網(wǎng)址里包含了50道數(shù)獨(dú)題，求每個(gè)解出的數(shù)獨(dú)題網(wǎng)格左上角的三位數(shù)之和，比如例圖的右圖就是483。

作為一位資深數(shù)獨(dú)愛好者，50道我都是用筆紙過的.?

編程模擬數(shù)獨(dú)求解網(wǎng)上好像已經(jīng)有很多模板了，大抵思路都是一個(gè)數(shù)字一個(gè)數(shù)字的填，填錯(cuò)了就回溯修改.? 比較實(shí)用的是宮回溯法，就是一宮填完后去下一宮填，這樣更容易發(fā)現(xiàn)錯(cuò)誤的數(shù)字，效率會(huì)高很多。

我前年的時(shí)候無聊嘗試實(shí)現(xiàn)了，被同學(xué)謔稱為“打印機(jī)回溯法”，思路是從左到右從上到下按1~9的順序逐個(gè)填入可能的數(shù)字，如果當(dāng)前位置填i出錯(cuò)誤，就將i換成i+1，如果直到i=9都是錯(cuò)的，那么回溯至上一個(gè)格子，將之變換為下一個(gè)數(shù)字，如果再不行繼續(xù)回溯。以此類推，事先標(biāo)記已給出的數(shù)字。

這個(gè)算法頗有些羞于見人. 不過是最常見的思維和最暴力的實(shí)現(xiàn)罷了，我也見過有的人將之當(dāng)作線性規(guī)劃問題賦予01變量來求解的，未嘗不是一種思路。

由于數(shù)獨(dú)相關(guān)算法 前人之述備矣，所以就不多提了，各位自己嘗試更好的思路實(shí)現(xiàn)吧。

ans：24702

Large non-Mersenne prime

Problem 97

The first known prime found to exceed one million digits was discovered in 1999, and is a Mersenne prime of the form 2^6972593?1; it contains exactly 2,098,960 digits. Subsequently other Mersenne primes, of the form 2^p?1, have been found which contain more digits.

However, in 2004 there was found a massive non-Mersenne prime which contains 2,357,207 digits: 28433×2^7830457+1.

Find the last ten digits of this prime number.

梅森素?cái)?shù)是形如2^p-1的素?cái)?shù)（p為素?cái)?shù)）

第一個(gè)超過一百萬位的素?cái)?shù)是在 1999 年發(fā)現(xiàn)的，并且是一個(gè)梅森素?cái)?shù)：?2^6972593?1;

它包含2098960 位。之后包含更多位的，形如2^p-1的梅森素?cái)?shù)被陸續(xù)發(fā)現(xiàn)。

在 2004 年人們發(fā)現(xiàn)了一個(gè)包含 2357207位的非梅森素?cái)?shù)：28433×2^7830457+1

求出這個(gè)素?cái)?shù)的最后十位。

最后10位，意味著計(jì)算只需保留后10位.

用乘法模擬指數(shù)，每次計(jì)算后取模即可，算是白給題了，不用快速冪都很快.

代碼較為簡單不放了 一個(gè)循環(huán)的事.

ans：8739992577

Anagramic squares

Problem 98

By replacing each of the letters in the word CARE with 1, 2, 9, and 6 respectively, we form a square number: 1296 = 36^2. What is remarkable is that, by using the same digital substitutions, the anagram, RACE, also forms a square number: 9216 = 96^2. We shall call CARE (and RACE) a square anagram word pair and specify further that leading zeroes are not permitted, neither may a different letter have the same digital value as another letter.

Using?words.txt?,?a 16K text file containing nearly two-thousand common English words, find all the square anagram word pairs (a palindromic word is NOT considered to be an anagram of itself).

What is the largest square number formed by any member of such a pair?

NOTE: All anagrams formed must be contained in the given text file.

words.txt：https://projecteuler.net/project/resources/p098_words.txt

用完全平方數(shù)?36^2=1296 來表示單詞 CARE? （C=1，A=2，R=9，E=6）

并取它的全排列可以得到另一個(gè)單詞RACE=9216=96^2

將 CARE（和 RACE）叫做一個(gè)平方變位詞對(duì)，并規(guī)定前置的 0 是不允許的，同時(shí)也不允許不同的字母用相同的數(shù)字替換。

words.txt?文件內(nèi)有近2000個(gè)單詞，找出其中所有的平方變位詞對(duì)（一個(gè)回文單詞不被認(rèn)為是它自己的變位詞）。
這些變位詞對(duì)中能形成的最大的平方數(shù)是多少？

注：所有的變位詞必須是文件中包含的單詞。

經(jīng)典模擬搜索實(shí)現(xiàn)類.

可以先對(duì)這個(gè)文件預(yù)處理一下，看看這之中最長的單詞。

文本中最長的單詞為14個(gè)字母：ADMINISTRATION，所以可確定平方數(shù)(n^2)n的上界為9938090? ?（因?yàn)檫@個(gè)單詞最大賦值為98765643293615.開跟取整后為9938090）

大體思路就是對(duì)于每個(gè)單詞，找單詞表中有沒有其他不同排列但字母相同的單詞，如果有，對(duì)這樣的每個(gè)其他排列單詞，先找原單詞的每個(gè)能匹配的平方數(shù)，然后將每個(gè)字母對(duì)應(yīng)的數(shù)字儲(chǔ)存，再把每個(gè)其他排列的單詞對(duì)應(yīng)的數(shù)字弄出來，檢驗(yàn)其是否為平方數(shù)，如果是那么動(dòng)態(tài)儲(chǔ)存兩個(gè)平方數(shù)中的大者給maxn，跑完所有其他排列單詞和每個(gè)其他排列單詞能對(duì)應(yīng)的匹配平方數(shù)，就能得到該原單詞所能得到的最大平方數(shù)，都莫得就返回0；

再在主函數(shù)用這個(gè)思路遍歷所有的單詞，找到最大的maxn

基于編了個(gè)略有些冗雜的代碼：

總的來說是一道不是很難的模擬題.做完后也沒啥感覺.

ans：18769

Largest exponential

Problem 99

Comparing two numbers written in index form like 211?and 37?is not difficult, as any calculator would confirm that 2^11?= 2048 < 3^7?= 2187.

However, confirming that 632382^518061?> 519432^525806?would be much more difficult, as both numbers contain over three million digits.

Using?base_exp.txt?, a 22K text file containing one thousand lines with a base/exponent pair on each line, determine which line number has the greatest numerical value.

NOTE: The first two lines in the file represent the numbers in the example given above.

base_exp.txt?：https://projecteuler.net/project/resources/p099_base_exp.txt

base_exp.txt?包含一千行內(nèi)容，每一行都包含一個(gè)基和一個(gè)指數(shù)，找出哪一行具有最大的值。

...

99題，作為破百撒花前的最后一道題...

水題，抬走，下一道！

取對(duì)數(shù)隨便比較. 主函數(shù)動(dòng)態(tài)替換最大值即可

709行的895447^504922是最大值。

ans：709

Arranged probability

Problem 100

If a box contains twenty-one coloured discs, composed of fifteen blue discs and six red discs, and two discs were taken at random, it can be seen that the probability of taking two blue discs, P(BB) = (15/21)×(14/20) = 1/2.

The next such arrangement, for which there is exactly 50% chance of taking two blue discs at random, is a box containing eighty-five blue discs and thirty-five red discs.

By finding the first arrangement to contain over 10^12?= 1,000,000,000,000 discs in total, determine the number of blue discs that the box would contain.

如果一個(gè)盒子里有 21 個(gè)有色的碟子，15 個(gè)藍(lán)色的和 6 個(gè)紅色的。從中隨機(jī)取兩個(gè)，可知取到兩個(gè)藍(lán)碟子的幾率是?(15/21)×(14/20) = 1/2.

下一個(gè)滿足此條件（即隨機(jī)取兩個(gè)碟子的情況下取到兩個(gè)藍(lán)色碟子的幾率是 50%）的情況是 85 個(gè)藍(lán)碟子和 35 個(gè)紅碟子。

對(duì)于包含超過10^12個(gè)碟子的情況中，滿足上述條件的并包含最少碟子的情況，該情況下共需要多少個(gè)藍(lán)碟子？

寫成代數(shù)分析一下.用x表示藍(lán)碟子數(shù)，n表示總碟數(shù)

1/2=x(x-1)/(n(n-1))

即2x(x-1)=n(n-1)，變化一下：2(2x-1)^2=(2n-1)^2+1?

令a=2x-1,b=2n-1，2a^2=b^2+1

即為b^2-2a^2=-1? 觀察之后發(fā)現(xiàn)這是個(gè)pell方程的變式.

是不是意外的很熟悉..66題的丟番圖變式...

先找到最小整數(shù)解：

那么對(duì)于原佩爾方程b^2-2a^2=1? D=2

用66題的連分?jǐn)?shù)展開易知根號(hào)2的連分?jǐn)?shù)為[1:(2)]

b^2-2a^2=1的最小正整數(shù)解為b=3,a=2

并且易知，若b,a為前一個(gè)方程的解，D為素?cái)?shù)時(shí)（則a,b必一奇一偶不妨令b為奇數(shù)a為偶數(shù)），那么令u^2=(b-1)/2? ? ?v^2=(a+1)/2D

2uv=b? 則（u,v）為后一個(gè)方程的最小整數(shù)解

再整理一下得到如果把根號(hào)D的第一個(gè)循環(huán)節(jié)寫出來，對(duì)應(yīng)的p/q就是b^2-2a^2=-1的解? 根號(hào)2的第一個(gè)循環(huán)節(jié)對(duì)應(yīng)的p,q為1/1，所以1,1就是其最小正整數(shù)解；

對(duì)于方程：Ax^2+Bx-Cy^2+Dy+E=0，

有形如

X(n)=aX(n-1)+bY(n-1)+c;

Y(n)=dX(n-1)+eY(n-1)+f

的通解。

所要做的只是需要根據(jù)前幾組解，把a(bǔ),b,c,d,e,f計(jì)算出來，然后循環(huán)求通解即可。

可以先跑出幾組解（循環(huán)搜索滿足b^2-2a^2=-1的數(shù)）

第一組解：1，1

第二組解：5，7

第三組解：29，41

第四組解：239，169

易知對(duì)于這道題若b^2-a^2=-1

那么a(n+1)=2bn+3an? ?b(n+1)=3bn+4an

循環(huán)遞推即可得到答案.

ans：756872327473

完結(jié)撒花.通過教學(xué)關(guān)了，希望各位能有所收獲。100題后就出新手村了o~

后續(xù)的更新嘛... 先失蹤個(gè)1年左右再說吧.