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

觀前聲明：? ???

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

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

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

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

第31題：

Coin sums

Problem 31

In the United Kingdom the currency is made up of pound (￡) and pence (p). There are eight coins in general circulation:

1p, 2p, 5p, 10p, 20p, 50p, ￡1 (100p), and ￡2 (200p).

It is possible to make ￡2 in the following way:

1×￡1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

How many different ways can ￡2 be made using any number of coins?

英國(guó)有8種硬幣1，2，5，10，20，50便士和1，2英鎊；那么組成200英鎊的方案有多少種？先不過(guò)個(gè)腦子.有八種幣，那么我們用8個(gè)變量代表8種幣的系數(shù)，用8個(gè)for跑一遍 判斷條件為如果a1x1+...+a8x8==200 那么方案數(shù)就加一：

int main()

{

int x1, x2, x3, x4, x5, x6, x7, count = 2;

for (x1 = 0; x1 <= 200; x1++)

for (x2 = 0; x2 <= 100; x2++)

for (x3 = 0; x3 <= 40; x3++)

for (x4 = 0; x4 <= 20; x4++)

for (x5 = 0; x5 <= 10; x5++)

for (x6 = 0; x6 <= 4; x6++)

for (x7 = 0; x7 <= 1; x7++)

if (x1 + 2 * x2 + 5 * x3 + 10 * x4 + 20 * x5 + 50 * x6 + 100 * x7 == 200)count++;

cout << count;

return 0;

}

快樂(lè)BF之后秒出了...但說(shuō)實(shí)話這個(gè)寫法著實(shí)看著丑.所以我們還是稍微分析一下。

考慮整系數(shù)等式a1x1+..+anxn=S，解這個(gè)，實(shí)際上就是取遍an可行范圍的所有值，把方程變?yōu)閍1x1+...+a(n-1)x(n-1)=S',S'=S-anxn? ?對(duì)每個(gè)可能的an分別解新的方程. 當(dāng)a1x1=Sx后，就確定只有一種解，返回1；所以思路就是不斷遞歸每個(gè)小方程，最后返回相加。實(shí)際上這也是BF..只是寫法上看著沒(méi)那么快了而已：

long long sequncefomula(int Ax[],int X[], int n, int S)

{

if (n == 1)return 1;

long long sumxn = 0;

for (X[n] = 0; X[n] <= S / Ax[n]; X[n]++)

sumxn += sequncefomula(Ax, X, n - 1, S - Ax[n] * X[n]);

return sumxn;

}

int main()

{

int Ax[9] = { 0,1,2,5,10,20,50,100,200 }, X[9], S = 200;

cout << sequncefomula(Ax, X, 8, S);

return 0;

}

ans:73682

第32題：

Pandigital products

Problem 32

We shall say that an?n-digit number is pandigital if it makes use of all the digits 1 to?n?exactly once; for example, the 5-digit number, 15234, is 1 through 5 pandigital.

The product 7254 is unusual, as the identity, 39 × 186 = 7254, containing multiplicand, multiplier, and product is 1 through 9 pandigital.

Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.

HINT: Some products can be obtained in more than one way so be sure to only include it once in your sum.

找到所有 a×b=c形式的c并加起來(lái)，其中等式滿足1~9都出現(xiàn)一次，比如39 × 186 = 7254。注意有些乘積可能不止有一種得到方法，確保算法能只計(jì)算其一次。

我們來(lái)想想怎樣找比較有效率.可能有些常年快樂(lè)BF的人已經(jīng)直接頭鐵兩個(gè)for算所有乘積再檢驗(yàn)了。但仔細(xì)想想，等式要求1~9都只出現(xiàn)一次，那么我們的搜索范圍只要在1~9的全排列內(nèi)找就行了。

將9個(gè)數(shù)字分隔成3各部分，第一個(gè)部分乘第二個(gè)部分若等于第三個(gè)部分則記錄；其中肯定有重復(fù)，但可以先記錄每一個(gè)滿足的結(jié)果之后再減去重復(fù)的。

而且，可以知道m(xù)與n位數(shù)的乘積位數(shù)為m+n或m+n-1，所以若以i,j來(lái)標(biāo)記0~8中的兩個(gè)分割點(diǎn)，則該分割中j必取4：如果把0~i當(dāng)成第一個(gè)數(shù)，i+1~j當(dāng)成第二個(gè)數(shù)，j+1~8當(dāng)成第三位數(shù)，則第一個(gè)數(shù)有i+1位，第二個(gè)數(shù)有j-i位，第三個(gè)數(shù)有8-j位，滿足i+1+j-i=8-j或8-j+1，j=4或3.5 取整j只能等于4。所以第三個(gè)部分的數(shù)一定是個(gè)4位數(shù)。

全排列相關(guān)的代碼在24題已經(jīng)說(shuō)過(guò)這里不再放出了，自己寫全排列也好調(diào)用next_permutation函數(shù)也好都行。要回看的往這走：全排列詳見24題。

這里只寫寫判斷.判斷可以先寫個(gè)i為變量的函數(shù) 無(wú)非就是把三部分從數(shù)組中取出做成數(shù)：

int checkAij(int A[9], int i, int j)//將0~i位乘i+1~j位判斷是否等于j+1~第8位;

{

if (j != 4)return 0;

int x1 = 0, x2 = 0, x3 = 0, k;

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

x1 += A[k] * pow(10, i - k);

for (k = i + 1; k <= j; k++)

x2 += A[k] * pow(10, j - k);

for (k = j + 1; k < 9; k++)

x3 += A[k] * pow(10, 8 - k);

if (x1 * x2 == x3)return x3;

return 0;

}

只要注意一下對(duì)應(yīng)的位數(shù)并調(diào)用質(zhì)數(shù)函數(shù)pow?

查看有無(wú)重復(fù)也不難，外部用一個(gè)數(shù)組儲(chǔ)存所有的4位數(shù)，如果該4位數(shù)滿足某個(gè)等式標(biāo)記之就行了。最后主函數(shù)中直接數(shù)這個(gè)數(shù)組。

ans:45228

第33題：

Digit cancelling fractions

Problem 33

The fraction?49/98?is a curious fraction, as an inexperienced mathematician in attempting to simplify it may incorrectly believe that?49/98?=?4/8, which is correct, is obtained by cancelling the 9s.

We shall consider fractions like,?30/50?=?3/5, to be trivial examples.

There are exactly four non-trivial examples of this type of fraction, less than one in value, and containing two digits in the numerator and denominator.

If the product of these four fractions is given in its lowest common terms, find the value of the denominator.

所有的2位數(shù)除以2位數(shù)的真分?jǐn)?shù)中，有4個(gè)分?jǐn)?shù)滿足去掉不同位的數(shù)字后分?jǐn)?shù)值保持不變，比如49/98，去掉不同位的9后4/8=49/98，找到所有的4個(gè)分?jǐn)?shù)，求出它們相乘約分后的分母。

即使在我現(xiàn)在做到的題中，這道的也算規(guī)模算非常小的了，也許可以手算？不過(guò)節(jié)能的我還是選擇了遍歷所有2位數(shù)除法然后判斷...

判斷函數(shù)：

int check(int x1, int x2)

{

double x3 = (double)x1 / x2;

int x11 = x1 / 10, x12 = x1 % 10, x21 = x2 / 10, x22 = x2 % 10;

if (x3 == ((double)x11 / x22)&&x12==x21)

return 1;

if (x3 == ((double)x12 / x21) && x11 == x22)

return 1;

return 0;

}

主函數(shù)中隨便跑跑即可。

這樣的分?jǐn)?shù)為16/64=1/4,26/65=2/5,19/95=1/5,49/98=4/8=1/2,乘積為1/100

不得不說(shuō)做歐拉計(jì)劃的題還是很長(zhǎng)見識(shí)的。

ans:100

第34題：

Digit factorials

Problem 34

145 is a curious number, as 1! + 4! + 5! = 1 + 24 + 120 = 145.

Find the sum of all numbers which are equal to the sum of the factorial of their digits.

Note: as 1! = 1 and 2! = 2 are not sums they are not included.

找到所有滿足本身等于其每個(gè)位置數(shù)字階乘之和的數(shù)字之和。注意1！與2！不算在內(nèi)。

先確定上界，注意到9999999>9!×7（7位數(shù)上界），而999999<9!×6，故上界為9999999

為了方便可以先用一個(gè)數(shù)組jie[10]保存0~9的階乘；之后便是主函數(shù)中從11跑起跑到9999999，逐個(gè)判斷過(guò)去；判斷方法按照定義.check函數(shù)可以這樣：

int sum=0,nx=n;

while(nx)

{

sum+=jie[nx%10];

nx/=10;

}

if(sum==n)return 1;

return 0;

主函數(shù)就懶得放了。跑出來(lái)只有2個(gè)數(shù)符合，145與40585。

ans:40730

第35題：

Circular primes

Problem 35

The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.

There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.

How many circular primes are there below one million?

循環(huán)質(zhì)數(shù)具有性質(zhì)：數(shù)的任意全排列為質(zhì)數(shù)，找到1000000以內(nèi)的所有循環(huán)質(zhì)數(shù)的個(gè)數(shù)。

看來(lái)這幾道系列題都重心都在數(shù)本身與數(shù)的位上的數(shù). 在c++里其實(shí)就是數(shù)組與數(shù)的互化；思路很清楚 篩一個(gè)質(zhì)數(shù)表 檢驗(yàn)每個(gè)質(zhì)數(shù)的全排列。最好是再開個(gè)數(shù)組記錄循環(huán)素?cái)?shù).但 我懶。

數(shù)組數(shù)，質(zhì)數(shù)歐拉篩，全排列..好像以前都講過(guò)了...不如這題就不放代碼了吧 （手動(dòng)[doge]

那么姑且說(shuō)一下結(jié)果，注意個(gè)位數(shù)的2，3，5，7也要算上；2位數(shù)題干中放了；3位數(shù)從113開始，一直到最大的6位數(shù)999331.

總共有55個(gè)

ans:55

不知為何感覺(jué)這5題比上5題水了不少...

再次聲明俺只提供部分的個(gè)人思考過(guò)程與關(guān)鍵算法.具體實(shí)現(xiàn)自己動(dòng)手豐衣足食.不然俺尋思著您這過(guò)來(lái)抄個(gè)答案有啥意思呢.這么累的搬運(yùn)個(gè)數(shù)據(jù)就能獲得物質(zhì)或精神上不菲的回報(bào)不成？

那么祝各位有所收獲.無(wú)論是在數(shù)學(xué)知識(shí)抑或碼風(fēng)寫法優(yōu)化上

有緣再見.