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

觀前聲明：?

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

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

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

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

第21題：

Amicable numbers

Problem 21

Let d(n) be defined as the sum of proper divisors of?n?(numbers less than?n?which divide evenly into?n).
If d(a) =?b?and d(b) =?a, where?a?≠?b, then?a?and?b?are an amicable pair and each of?a?and?b?are called amicable numbers.

For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.

Evaluate the sum of all the amicable numbers under 10000.

定義數d(n)為n的所有因子之和，如果d(a)=b且d(b)=a且a≠b則稱a,b為一個amicable pair，并且稱a,b均為amicable numbers（菜的不知道咋翻譯，親和數？）

例如220和284就是一對amicable numbers；找到10000以內所有的amicable numbers。

基本思路都是從定義入手(大概)，實現起來的方法姑且有兩種（能直接找出來的神仙論外），一種是對于每個數找到它的因數之和，如果不為本身再去判斷該和的因數之和，如果是一對親和數那么加起來，接著跑，屬于直接從定義入手的頭鐵法；另一種是先用個數組記錄完所有數字的因子之和，sumfac[n]就代表d(n)，然后再去進行愉快的每個都是o(1)的遍歷判斷，這個數組記錄的方法就很有技巧了（雖說在后期屬于基操），逆向思維來看，對于每個數n，它必定是k*n(k>2)的因子，那么循環(huán)從1開始到10000，對于每個數n，再用一個循環(huán)使sumfac[k*n]+=n（k*n≤10000），全部跑完時就獲得了10000以內每個數字的因子和。

綜上得到2個算法：

頭鐵：

int sumfac(int n)

{

int i, sum = 0;

for (i = 1; i <= n / 2; i++)

if (n % i == 0)sum += i;

return sum;

}

int check(int n)

{

if ((sumfac(sumfac(n)) == n) && (sumfac(n) != n))return 1;

return 0;

}

優(yōu)化后：

void getsumfac(void)//maxn取10000，在主函數中調用該函數即可

{

int n;

for (n = 1; n <= maxn; n++)

for (int k = 2; n * k <= maxn; k++)

sumfac[k * n] += n;

}

之后的判斷和主函數就自己寫吧.無非類似頭鐵法中的check。

ans:31626(只有5對 頭鐵找起來也不慢)

第22題：

Names scores

Problem 22

Using?names.txt?(right click and 'Save Link/Target As...'), a 46K text file containing over five-thousand first names, begin by sorting it into alphabetical order. Then working out the alphabetical value for each name, multiply this value by its alphabetical position in the list to obtain a name score.

For example, when the list is sorted into alphabetical order, COLIN, which is worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the list. So, COLIN would obtain a score of 938 × 53 = 49714.

What is the total of all the name scores in the file?

https://projecteuler.net/project/resources/p022_names.txt

放一個截圖感受下我第一次見到這種數據的內心波動:

這個網址中給了超過5000個名字，我們要先把這5000個名字按照字母順序排序，然后再按照他給出的計算方法算出每個名字的分，再把這些分加起來即為最后答案，比如COLIN排完序后是第938個名字，按照每個字母對應的數字順序（A對應1，B對應2，以此類推）COLIN的分數就是(3 + 15 + 12 + 9 + 14)*938=49714

emmm是不是感覺無從下手？其實就那么照定義做就行了，這類模擬題基本上都是莫得操作的

如果不會freopen函數建議下個notepad處理數據，把這些名字儲存到一個字符串數組string s[]里，然后使用c++自帶的排序函數sort直接字母排序(注意開頭要包含庫#include<algorithm>，簡直c++福音，終于能用一次內置函數了)

把具體多少個名字自己跑一遍，存在s[len]里，s[i]代表第i個名字，sort的使用方法為sort(s,s+len)；之后的計算每個字母的分數也直接算即可，比如計算字母K對應的數字，那么直接'K'-'A'+1，'K'-'A'會用它們的字符對應的ascii碼相減，因為A是第一個大寫字母所以要加1，而加1后自動把char型數據轉化為整型.代碼如下：

int main()

{

int len = 0;

long long sum = 0;

while (1)?

{

if (s[len].size() > 0)?

len++;

else break;

}

sort(s, s + len);

for (int i = 0; i < len; i++)?

{

int temp = 0;

for (int j = 0; j < s[i].size(); j++)

temp += s[i][j] - 'A' + 1;

sum += temp * (i + 1);

}

cout << sum << endl;

return 0;

}

s就是字符串數組

ans:871198282

第23題：

Non-abundant sums

Problem 23

A perfect number is a number for which the sum of its proper divisors is exactly equal to the number. For example, the sum of the proper divisors of 28 would be 1 + 2 + 4 + 7 + 14 = 28, which means that 28 is a perfect number.

A number?n?is called deficient if the sum of its proper divisors is less than?n?and it is called abundant if this sum exceeds?n.

As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16, the smallest number that can be written as the sum of two abundant numbers is 24. By mathematical analysis, it can be shown that all integers greater than 28123 can be written as the sum of two abundant numbers. However, this upper limit cannot be reduced any further by analysis even though it is known that the greatest number that cannot be expressed as the sum of two abundant numbers is less than this limit.

Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.

定義：perfect number:n的因子之和等于n；deficient number:n的因子之和小于n；abundant number：n的因子之和大于n

找到所有不能被分解為2個abundant number之和的正整數之和。

題干還告訴我們通過數學分析可以知道所有大于28123的數字都存在這樣的分解（這應該是數論的知識了 有興趣者自己證證）

剛剛21題的sumfac數組馬上就能派上用場了，上界也很人性化的告訴我們了：maxn=28123

如果sumfac[n]>n數組儲存A[n]=1，表示是abundant number，否則為0；那么剩下的就是判斷的事，對于一個數n，遍歷所有A[n-i]與A[i]，如果存在這樣的i使得A[i]與A[n-i]都為1，那么說明n能被分解，否則不能，主函數循環(huán)中sum+=n：

for (n = 2; n <= 28123; n++)

{

int cum = 0;

for (i = 1; i <= n / 2; i++)

if (A[i] && A[n - i])?

{

cum = 1; break;

}

if (!cum)sum += n;

}

ans:4179871

第24題：

Lexicographic permutations

Problem 24

A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:

012? ?021? ?102? ?120? ?201? ?210

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

全排列問題.記01234567為第一個排列，按照字典排序法，第1000000個排序是啥。

你以為我會告訴你c++自帶字典排序next_permutation嗎.()

關于next_permutation的用法，首先要包含庫#include<algorithm>，然后對于一個數組A，

如果A[3]={0,1,2}，那么調用next_permutation(A,A+3)A就會變成{0,2,1}，A+3表示字典排序A數組從第一個字符開始的長度；需要注意的是，如果A已為最后一種排序{2,1,0}那么再使用這個函數后它就會變成{0,1,2}即接著循環(huán)升序。（另一個對應函數為prev_permutation）

在主函數中調用999999次這個函數就能得到答案所需的排序，不過，若是就這樣得到答案那恐怕也不會覺得這題有啥意思吧。我們試試手動模擬字典排序，我順便科普一下字典排序實際運算規(guī)則：

1.從右往左找第一個位置為i的數，這個數滿足A[i]<A[i+1]

2.從右往左找第一個大于A[i]的數，其位置為j（j>i）

3.交換A[i],A[j]的值

4.對i以后的數按從小到大順序排列。

比如2143，第一個滿足A[i]<A[i+1]的數為1，標記1的位置為2（便于理解用邏輯序，代碼中要注意是A[1]=1），第一個大于1的數為3，交換位置得到2341，然后將第二個位置后的數字從小到大排列得到2314；

實現起來也不復雜：

//排序函數sort其實這個庫里也是自帶的，但順手就寫了冒泡，用快排或者其他均可。

void changeij(int A[10],int i,int j)

{

int temp = A[i];

A[i] = A[j];

A[j] = temp;

}

void sort(int A[10], int start, int end)//冒泡排序

{

int i, j;

for (i = 0; i <= end - start; i++)

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

{

if (A[j] > A[j + 1])

changeij(A, j, j + 1);

}

}

void changenext(int A[10])

{

int i, j;

for (i = 8; i >= 0; i--)

if (A[i] < A[i + 1])break;

for (j = 9; j > i; j--)

if (A[j] > A[i])break;

changeij(A, i, j);

sort(A, i + 1, 9);

}

ans:2783915460

第25題：

1000-digit Fibonacci number

Problem 25

The Fibonacci sequence is defined by the recurrence relation:

Fn?= Fn?1?+ Fn?2, where F1?= 1 and F2?= 1.

Hence the first 12 terms will be:

F1?= 1
F2?= 1
F3?= 2
F4?= 3
F5?= 5
F6?= 8
F7?= 13
F8?= 21
F9?= 34
F10?= 55
F11?= 89
F12?= 144

The 12th term, F12, is the first term to contain three digits.

What is the index of the first term in the Fibonacci sequence to contain 1000 digits?

第12個斐波那契數是第一個達到3位數的斐波那契數，那么第一個達到1000位的斐波那契數是第幾個斐波那契數？

嗯，1000位，想必都意識到了吧，讓我看看是誰在拉垮，o是我們的c++~

那么這道題用大整數做也不難。用二維數組記錄斐波那契數

設F[n][]表示第n個斐波那契數，原理與之前的大整數加法類似，F[n][0]為第n個的位數，F[n][1]為它的個位數，以此類推一直到F[n][F[n][0]]。不斷計算直到某個n的F[n][0]大于等于1000為止

void sumfabonacin(int A[10000][10000],int n)

{

int i;

for (i = 0; i <= A[n - 1][0]; i++)//這里以及下一個的for都是在算Fn?= Fn?1?+ Fn?2

A[n][i] = A[n - 1][i];

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

A[n][i] += A[n - 2][i];

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

{

if (A[n][i] < 10)continue;

A[n][i + 1] += A[n][i] / 10;

A[n][i] %= 10;

A[n][0] += (i == A[n][0]);

}

}

int main()

{

int n = 3;

A[1][0] = 1, A[1][1] = 1;

A[2][0] = 1, A[2][1] = 1;

while (1)

{

sumfabonacin(A, n);

if (A[n][0] >= 1000)break;

n++;

}

cout << n;

return 0;

}

ans:4782

不知各位有無感覺到比起前面的幾題現在難度稍微增加了些許呢？

那么.有緣再見.