关于啥是Project Euler 详见 https://projecteuler.net/about  

观前声明： 

1.   这是个人兴趣使然的对自己入坑pe的记录，仅提供思路和部分代码；各个方面肯定都是有着优化与提升空间的，甚至在许多大佬看来这应该是初学者的浅薄而未经剪枝的丑码，如果能帮到有兴趣的人自是最好，也欢迎能醍醐灌顶的深度讨论。

2. 大佬看到了笑笑就行，还请轻喷。

3. 带着恶意，抬杠者...俺也喷不过您，也不能拿您咋样...毕竟这只是我个人兴趣使然的行为或者说是学习记录分享。 （说是记录，但因为是早先写的所以其实是在各种意义上公开处刑和吐槽自己 并尝试补救优化）

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)的因子，那么循环从1开始到10000，对于每个数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;

}

优化后：

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能被分解，否则不能，主函数循环中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}即接着循环升序。（另一个对应函数为prev_permutation）

在主函数中调用999999次这个函数就能得到答案所需的排序，不过，若是就这样得到答案那恐怕也不会觉得这题有啥意思吧。我们试试手动模拟字典排序，我顺便科普一下字典排序实际运算规则：

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

不知各位有无感觉到比起前面的几题现在难度稍微增加了些许呢？

那么.有缘再见.