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

观前声明：

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

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

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

4. 语言是c++，用的VS平台

第16题：

Power digit sum

Problem 16

2^15 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.

What is the sum of the digits of the number 2^1000?

求出2的1000次方每位数的和.

这种大整数类型的题.简直是在难为c++（也还好.），因为python可以直接算出2^1000，java自带大整数类，而咱的c++啥都莫得要自己想办法，直接pow(2,1000)不用想肯定是会溢出的

放个python的写法:

sum = 0

for n in str(2**1000): 

sum += int(n) print sum

所以俺只能用数组模拟大整数，在之前的题也用过类似的思路了，就是用A[0]存放数的位数，然后A[1]储存个位数，A[2]储存十位数，一直储存到A[A[0]]；（有兴趣还闲得发慌的人可以用数组模拟大整数4则运算，也不是啥难事.存个模板以后用起来也很方便）

而这里只要求计算2^n，所以这个数组对应的函数也很简单，就是将A[1]到A[A[0]]都乘2，然后进位处理，如果位数变化改变A[0]即可：

void sum(int A[1000])//A[0]存储位数,逆序自加;

{

    int i;

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

        A[i] *= 2;

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

    {

        if (A[i] < 10)continue;

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

        A[i] %= 10;

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

    }

}

在主函数中令A[0]=1,A[1]=2,循环调用该函数999次，再求每位数的和即可.

算是比较暴力但清晰的思路了，好在规模不大可以秒出

需要注意的是，像A[]这种大数组尽量放在全局，不要放在函数内，放在函数内部是一个很不好的习惯，因为2^1000的位数上界不过1000，所以设置数组A[1000]是没有问题的。

ans:1366

第17题：

Number letter counts

Problem 17

If the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.

If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?

NOTE: Do not count spaces or hyphens. For example, 342 (three hundred and forty-two) contains 23 letters and 115 (one hundred and fifteen) contains 20 letters. The use of "and" when writing out numbers is in compliance with British usage.

1到1000全用英文字母（英式）表示，然后数字母个数.(不算空格与划线)

简单模拟题，写个函数判断数字n的字母个数然后循环跑一遍即可

再不然，纸笔手算也不算复杂.无非列出大致的几种情况加一下.

因为上界是1000，one thousand有11个字母，所以我们跑到999最后加上11就行了；

将n分解为百位n1十位n2与个位n3：

int n1 = n / 100, n2 = (n / 10) % 10, n3 = n % 10;

然后用3个数组分别表示0~9，10~19，20~90字母数字范围（因为所有1000内数字都可通过这三个的组合与and和划线来表示，比如143，one hunderd and forty-three，1对应0~9，4对应20~90，3再对应0~9）

int numberx1[10] = { 0,3,3,5,4,4,3,5,5,4 };//0~9单词字母数;只要用到后面9个（c++数组物理序是从0开始数的不会有人不知道吧....），第0个设为0(one~nine)

int numberx21[10] = { 3,6,6,8,8,7,7,9,8,8 };//10~19;(ten~nineteen)

int numberx22[10] = { 0,0,6,6,5,5,5,7,6,6 };//20~90;同上，只要用到后面8个;(twenty~ninety)

（这部分小心点数别数错.顺便 当时写的时候才知道自己英语居然这么差.）

然后就开始分类讨论吧 如果n1不为0，则说明是3位数，那么就要加上hundred （7个字母）和第一个数组的[n1]；为0则不加；

然后讨论n2为0，为1和大于1的情况，n3代入的数组依赖于n2的取值情况.细节懒得讨论了自己想想不难的，姑且放出部分代码：

int x1, x2;

x1 = numberx1[n1];

if (x1)x1 += 7;//n1 hunderd and...;

if (n2 == 1)x2 = numberx21[n3];

if (n2 > 1)x2 = numberx22[n2] + numberx1[n3];

if (n2 == 0)x2 = numberx1[n3];

if (x1&&x2)return x1 + x2 + 3;//and有3位字母;

else return x1 + x2;

其余部分包括主函数随便写写即可；

手算：

one 3 -two 3 -three 5 -four 4 -five 4 -six 3 -seven 5 -eight 5 -nine 4 = 36

ten 3 -eleven 6- twelve 6 -thirteen 8 -fourteen 8 -fifteen 7 -sixteen 7 -seventeen 9 -eighteen 8- nineteen 8 = 70

twenty 6 -thirty 6 -forty 5 -fifty 5 -sixty 5 -seventy 7 -eighty 6 -ninety 6 = (46 * 10)  + (36 * 8) = 460 + 288 = 748

1~99=36+70+748=854；

只有1个hundred(7个字母，100，200，...900):

7*9+36=99

hundred+and（10个字母）（不考虑前面hunderd前面的数字，100，110，..990与1~9）:

10*99*9=8910

只考虑hunderd前面的数字（1~9作为百位，每个百位有99种情况）：

36*99=3564

所有百位后的1~99：

854*9=7696

1000：

11

全加起来：

ans:21124

第18题：

Maximum path sum I

Problem 18

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3
7 4
2 4 6
8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom of the triangle below:

75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

手机端图看这里：

NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)

对于这样一个数字组成的三角阵，从顶元素开始往下加，每次只能左下或右下进行加法运算，加到底层时最大数字为多少；这道题只有16384种情况，暴搜起来也不慢，但是pe67作为同类型的题有100行，就无法暴搜了。

实际上，这是个很经典的动态规划问题。

把这坨东西写成下三角矩阵的形式：

a11

a21  a22

a31  a32   a33

....

不难发现，若令ost[i][j]表示从i行第j列出发到底层的路径最大值

则ost[i][j]=A[i][j]+max(ost[i+1][j],ost[i+1][j+1])(i<n)  ;ost[n][j]=A[n][j]

那么思路就很简单了，从最后一行开始，不断取二者中的最大值向上给ost[i][j]赋值.

ost[0][0]即为所求.（实际上这是由底至顶的状态转移方程.详细可以去学运筹学的动态规划.）

int ost[100][100] = { 0 };

void getost(int i, int j)

{

if (i == 14)ost[i][j] = A[i][j];

else ost[i][j] = A[i][j] + (ost[i + 1][j] > ost[i + 1][j + 1] ? ost[i + 1][j] : ost[i + 1][j + 1]);

}

int main()

{

for (int i = 14; i >= 0; i--)

for (int j = 0; j <=i; j++)

getost(i, j);

cout << ost[0][0];

return 0;

}

ans:1074

第19题：

Counting Sundays

Problem 19

You are given the following information, but you may prefer to do some research for yourself.

• 1 Jan 1900 was a Monday.

• Thirty days has September,
  April, June and November.
  All the rest have thirty-one,
  Saving February alone,
  Which has twenty-eight, rain or shine.
  And on leap years, twenty-nine.

• A leap year occurs on any year evenly divisible by 4, but not on a century unless it is divisible by 400.

How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?

1901年1月1日开始到2000年12月31日有多少个星期天在每月初的第一天？

上面的英文有额外告诉我们的已知情况，不过除了1900年的1月1日是周一外没啥特别有用的

又是这种咋一看有意思但实际写起来提不起兴趣的模拟题.因为我一般用c++写模拟题都又臭又长（我水平有限）

简单介绍下手算法...无非是像上题那样把所有情况考虑一下该加加该减减注意闰年.就不多说了 感兴趣者自己算算也不难。

如果要代码的话那么怎么敲呢. 实际上这题我写了个比较蠢的代码

简单推算知1901.1.1是周一，到2000.12.31共36524天。

若某年某月的天数模7等于x，那么如果这月从周n开始，下月的起始天为周（x+n）%7  （周0算作周天）

那么先写个求某年某月当月天数的函数getdaynum；再用这个函数写个求当月月初是周几的函数days

int getdaynum(int year, int month)//这个考虑好闰年即可，不难写；

{

if (year % 4 == 0 && year % 400 == 0)

if (month == 2)return 29;

if (month == 2)return 28;

if (month == 4 || month == 6 || month == 9 || month == 11)return 30;

return 31;

}

对于days(int year,int month)函数，我们知道，如果是1901年1月，则返回1；

如果是其他年月，那么则返回（上一个月的天数+上月的起始周）%7

int days(int year, int month)

{

if (year == 1901 && month == 1)return 1;

if (month == 1)return (days(year - 1, 12) + getdaynum(year - 1, 12) ) % 7;

return (days(year, month - 1) + getdaynum(year, month - 1)) % 7;

}

实际上我这写法也不好，应该在函数外再建一个数组储存，直接调用数组的，这种暴力递归如果在主函数直接跑实际上会白跑很多趟. 不过当时比现在还傻.现在又懒得改了，大家注意一下就行。

ans:171

第20题：

Factorial digit sum

Problem 20

n! means n × (n − 1) × ... × 3 × 2 × 1

For example, 10! = 10 × 9 × ... × 3 × 2 × 1 = 3628800,
and the sum of the digits in the number 10! is 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27.

Find the sum of the digits in the number 100!

算出100！每个位数数字的和。

又是这类大正数问题，又到了c++拉跨时间。

还记得之前的写的大整数加法吗.大整数乘法也不难写.但当时的我明显想偷懒，所以稍微改了一下大整数加法变成加法实现的简易阶乘（大整数乘法的话后面有些题迟早要放的 现在在姑且让我节一下能）

大整数加法再放送：

void sum(int A[1000],int B[1000])//A[0]存储位数,逆序加;

{

    int i;

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

        A[i] += B[i];

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

    {

        if (A[i] < 10)continue;

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

        A[i] %= 10;

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

    }

}

n!等于（n-1）！个n相加

所以只要写个n-1个A[]自加的函数(A,n)，循环调用n次(A,i)（i从n到1）即可

void valve(int A[1000], int n)//自加n-1次;

{

    int i;

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

        B[i] = A[i];

    for (i = 1; i < n - 1; i++)

        sum(A, B);

}

int main()

{

    int i, j, sum = 0;

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

    for (i = 100; i > 0; i--)//简易阶乘;

        valve(A, i);

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

        sum += A[i];

    cout << sum;

    return 0;

}

所幸规模不大基本秒出. 但这种写法极其偷懒，大家还是自己思考下怎么模拟大整数的乘法吧.当然以后俺也会放出来的（如果还有以后的题的话）

ans:648

那么.有缘再见