關(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)

觀前提示：本期為水題。后幾題出現(xiàn)n角形數(shù)間的科普.

第41題：

Pandigital prime

Problem 41

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, 2143 is a 4-digit pandigital and is also prime.

What is the largest?n-digit pandigital prime that exists?

還是之前的定義，如果n位數(shù)由1~n組成那么這個(gè)數(shù)字就是個(gè)pandigital number（泛數(shù)字的？）比如2143是4位數(shù)的pandigital number并且還是個(gè)質(zhì)數(shù)；找到最大的具有此性質(zhì)的n位數(shù)質(zhì)數(shù)。

首先n是小于等于9的；然后它是個(gè)質(zhì)數(shù)，我們可以由此繼續(xù)縮小范圍；因?yàn)槔右呀?jīng)舉了一個(gè)4位數(shù)，所以我們要找的數(shù)字肯定大于等于4位數(shù)。

我們來看5位數(shù)，每位數(shù)字之和為1+2+3+4+5=15為3的倍數(shù)，所以所有的具有此性質(zhì)的5位數(shù)不可能是質(zhì)數(shù)；6位數(shù)：1+2+3+4+5+6=21，8位數(shù)：1+2+3+4+5+6+7+8=36，9位數(shù)：1+2+3+4+5+6+7+8+9=45，同理，6位數(shù)，8位數(shù)，9位數(shù)都不在考慮范圍內(nèi)，我們要找的數(shù)只可能是4位數(shù)或7位數(shù)。

直接看7位數(shù)：

那么剩下的事就是跑一個(gè)質(zhì)數(shù)表，檢驗(yàn)所有7位數(shù)質(zhì)數(shù)，把每個(gè)7位數(shù)質(zhì)數(shù)變成數(shù)組表達(dá)，看是否1~7都出現(xiàn)了。

或者：數(shù)組從1234567開始字典排序，對(duì)于每個(gè)排序數(shù)組化為數(shù)字檢驗(yàn)是否為質(zhì)數(shù)。

關(guān)于實(shí)現(xiàn)這些的代碼之前的題中都有而且也不難，懶得再說了撒。

ans:7652413

Coded triangle numbers

Problem 42

The?nth?term of the sequence of triangle numbers is given by,?tn?= ?n(n+1); so the first ten triangle numbers are:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

By converting each letter in a word to a number corresponding to its alphabetical position and adding these values we form a word value. For example, the word value for SKY is 19 + 11 + 25 = 55 =?t10. If the word value is a triangle number then we shall call the word a triangle word.

Using?words.txt?(right click and 'Save Link/Target As...'), a 16K text file containing nearly two-thousand common English words, how many are triangle words?

把字母A~Z對(duì)應(yīng)數(shù)字1~26，那么SKY的值就等于19+11+25=55，這正好是第10個(gè)三角數(shù)（第n個(gè)三角數(shù)為n(n+1)/2），把這樣的單詞稱為三角單詞。

在words.txt：https://projecteuler.net/project/resources/p042_words.txt

網(wǎng)址里有近2000個(gè)英語單詞，算出其中有多少個(gè)三角單詞。

在22題中也需要算單詞值.這題比起22可能還更簡(jiǎn)單些。單詞值用char[]或者string按定義算就完事了，類似代碼能在22題中找到不贅述了。

檢驗(yàn)值是否為三角數(shù)，那不就反過來驗(yàn)證A=n(n+1)/2的n是否為整數(shù)，變換一下：

（(根號(hào)(8A+1))-1）/2為整數(shù)那么A就為三角數(shù)；如果不嫌麻煩也可以o(n)判斷，就是在一個(gè)范圍內(nèi)逐個(gè)檢驗(yàn)A是否等于某個(gè)n對(duì)應(yīng)的三角數(shù)：

As：

for (n = 0; n < 50; n++)

As[n] = n * (n + 1) / 2;

int checkstr(string s,int As[50])

{

int i, length = s.size(), sum = 0;

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

sum += s[i] - 'A' + 1;

for (i = 1; i < 50; i++)

if (sum == As[i])return 1;

return 0;

}

把近2000個(gè)單詞存進(jìn)string[]數(shù)組里，然后逐個(gè)檢驗(yàn)即可。存進(jìn)數(shù)組要么freopen函數(shù)讀要么自己手動(dòng)復(fù)制。

ans:162

第43題：

Sub-string divisibility

Problem 43

The number, 1406357289, is a 0 to 9 pandigital number because it is made up of each of the digits 0 to 9 in some order, but it also has a rather interesting sub-string divisibility property.

Let?d1?be the 1st?digit,?d2?be the 2nd?digit, and so on. In this way, we note the following:

• d2d3d4=406 is divisible by 2

• d3d4d5=063 is divisible by 3

• d4d5d6=635 is divisible by 5

• d5d6d7=357 is divisible by 7

• d6d7d8=572 is divisible by 11

• d7d8d9=728 is divisible by 13

• d8d9d10=289 is divisible by 17

Find the sum of all 0 to 9 pandigital numbers with this property.

1406357289是個(gè)奇妙的數(shù)字，從2開始的連續(xù)三位數(shù)字提取出來都能被連續(xù)的質(zhì)數(shù)整除，詳細(xì)見上。找到所有具有此性質(zhì)的由0~9組成的數(shù)字的和。

神奇歸神奇，字典排序、提取數(shù)字都是之前講過的了，該頭鐵該亂寫還是很容易水的。

字典排序不說了，說說檢驗(yàn)，先用數(shù)組C[]存對(duì)應(yīng)要除以的質(zhì)數(shù)，如果數(shù)組B[]為某個(gè)排列的0~9，那么檢驗(yàn)函數(shù)可以這么寫：

int changeinter(int A[], int start, int end)//數(shù)組提取數(shù)字之前也寫過的。

{

int i, j, sum = 0;

for (i = start, j = end - start; i <= end; i++, j--)

sum += A[i] * pow(10, j);

return sum;

}

int check(int A[10])//檢驗(yàn)函數(shù);

{

int B[7] = { 0 }, i, C[7] = { 2,3,5,7,11,13,17 };

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

B[i] = changeinter(A, i + 1, i + 3);

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

if (B[i] % C[i])return 0;

return 1;

}

因?yàn)橐蠛?，而我們開始就在使用數(shù)組和字典排序函數(shù)來儲(chǔ)存全排列，所以求和可以直接用大整數(shù)的加法，因?yàn)槎荚跀?shù)組里；

先用while把所有的0~9字典排序檢驗(yàn)完并全部按位加到數(shù)組sum[]里，最后再進(jìn)位處理：

（這里我用的之前自己寫的字典排序函數(shù)，也可用algorithm庫自帶的next_permutation函數(shù)，相關(guān)代碼及說明24題有：21~25）

while (count <= 3628800)//10!種排列;

{

if (check(A))

{

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

cout << A[i];

cout << endl;

for (i = 1; i <= 10; i++)

sum[i] += A[10 - i];

}

changenext(A, 10);

count++;

}

for (i = 1; i <= sum[0]; i++)

{

if (sum[i] < 10)continue;

sum[i + 1] += sum[i] / 10;

sum[i] %= 10;

sum[0] += (i == sum[0]);

}

for (i = sum[0]; i > 0; i--)

cout << sum[i];

ans：16695334890

第44題：

Pentagon numbers

Problem 44

Pentagonal numbers are generated by the formula, Pn=n(3n?1)/2. The first ten pentagonal numbers are:

1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...

It can be seen that P4?+ P7?= 22 + 70 = 92 = P8. However, their difference, 70 ? 22 = 48, is not pentagonal.

Find the pair of pentagonal numbers, Pj?and Pk, for which their sum and difference are pentagonal and D = |Pk?? Pj| is minimised; what is the value of D?

五角形數(shù)：Pn=n(3n?1)/2，找到這樣一對(duì)五角形數(shù)Pj和Pk，它們的和與差均為五角形數(shù)，且它們的差的絕對(duì)值D是所有的這樣的五角形數(shù)對(duì)中最小的，求出D。

其實(shí)這道題俺也沒啥特別好的思路，這個(gè)最小的D怎么找呢，對(duì)于一個(gè)五角形數(shù)Pk，如果所有小于它的五角形數(shù)組成的五角形數(shù)對(duì)都不具有和與差為五角形數(shù)的性質(zhì)，那么若Pk與某個(gè)小于Pk的Pj具有和與差為五角形數(shù)的性質(zhì)，則Pk與Pj的差的絕對(duì)值就為最小的D。

所以我們令Pk第二個(gè)五角形數(shù)開始，每次Pj都從Pk的前一個(gè)五角形數(shù)向前搜索判斷是否具有此性質(zhì)，一旦找到，由我們的查找規(guī)則，那么Pj與Pk的差的絕對(duì)值就是最小的D。

為了方便，我們找的時(shí)候用n1，n2作為五角形數(shù)對(duì)應(yīng)的序列，n(3n?1)/2就是對(duì)應(yīng)的五角形數(shù)。而檢驗(yàn)一個(gè)數(shù)是否為五角形數(shù)也很簡(jiǎn)單，k=n(3n?1)/2變換一下：根號(hào)（1+24*k）+1為一個(gè)整數(shù)，對(duì)應(yīng)代碼：

int check(int np)//檢驗(yàn)是否為五角形數(shù);

{

double n = (pow(24 * np + 1, 0.5) + 1) / 6;

if (n == int(n))return 1;

return 0;

}

int patan(int n)//第n個(gè)五角形數(shù)

{

return n * (3 * n - 1) / 2;

}

主函數(shù)：

int main()

{

int n1, n2;

for (n1 = 2;; n1++)

{

int checkn = 0;

for (n2 = n1 - 1; n2 > 0; n2--)

{

if (check(patan(n1) + patan(n2)) && check(patan(n1) - patan(n2)))

{

checkn = 1; break;

}

}

if (checkn)break;

}

cout << n1 << " " << n2 << " " << patan(n1) - patan(n2);

return 0;

}?

由搜索規(guī)則找到的第一個(gè)五角形數(shù)對(duì)就是所求。

因?yàn)橐?guī)模小，暴搜很快：答案為第2167與第1020個(gè)五角形數(shù)組成的數(shù)對(duì)。

ans：5482660

第45題：

Triangular, pentagonal, and hexagonal

Problem 45

Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:

Triangle?Tn=n(n+1)/2?1, 3, 6, 10, 15, ...

Pentagonal?Pn=n(3n?1)/2?1, 5, 12, 22, 35, ...

Hexagonal?Hn=n(2n?1)?1, 6, 15, 28, 45, ...

It can be verified that T285?= P165?= H143?= 40755.

Find the next triangle number that is also pentagonal and hexagonal.

（tri,penta,hexa....這些前綴我都是通過某聯(lián)盟知道的（霧））

三角形數(shù)：Tn=n(n+1)/2；五角形數(shù)：Pn=n(3n?1)/2；六角形數(shù)：Hn=n(2n?1)

第285個(gè)三角形數(shù)=第165個(gè)五角形數(shù)=第143個(gè)六角形數(shù)=40755。

找到下一個(gè)既是五角也是六角形數(shù)的三角形數(shù)。

完全意義上的水題...六角形是步長最大的，對(duì)后每個(gè)六角形數(shù)檢驗(yàn)是否為三角形數(shù)或和角形數(shù)即可。注意到六角形數(shù)Hn=n(2n?1)=(2n)(2n-1)/2 所以所有的六角形數(shù)都是三角形數(shù)...只需要檢驗(yàn)五角形數(shù)就行了。

隨便跑跑：

int checkpen(long long np)//檢驗(yàn)是否為五角形數(shù);

{

double n = (pow(24 * np + 1, 0.5) + 1) / 6;

if (n == int(n))return 1;

return 0;

}

long long hex(long long n)

{

return n * (2 * n - 1);

}

int main()

{

long long n;

for (n = 144;; n++)

if (checkpen(hex(n)))break;

cout << hex(n);

return 0;

}?

ans：1533776805

就到這里撒。

下期就要滿50題了啦~

（前提是有緣更下期）