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

观前声明：     

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

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

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

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

第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?

英国有8种硬币1，2，5，10，20，50便士和1，2英镑；那么组成200英镑的方案有多少种？先不过个脑子.有八种币，那么我们用8个变量代表8种币的系数，用8个for跑一遍 判断条件为如果a1x1+...+a8x8==200 那么方案数就加一：

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;

}

快乐BF之后秒出了...但说实话这个写法着实看着丑.所以我们还是稍微分析一下。

考虑整系数等式a1x1+..+anxn=S，解这个，实际上就是取遍an可行范围的所有值，把方程变为a1x1+...+a(n-1)x(n-1)=S',S'=S-anxn   对每个可能的an分别解新的方程. 当a1x1=Sx后，就确定只有一种解，返回1；所以思路就是不断递归每个小方程，最后返回相加。实际上这也是BF..只是写法上看着没那么快了而已：

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并加起来，其中等式满足1~9都出现一次，比如39 × 186 = 7254。注意有些乘积可能不止有一种得到方法，确保算法能只计算其一次。

我们来想想怎样找比较有效率.可能有些常年快乐BF的人已经直接头铁两个for算所有乘积再检验了。但仔细想想，等式要求1~9都只出现一次，那么我们的搜索范围只要在1~9的全排列内找就行了。

将9个数字分隔成3各部分，第一个部分乘第二个部分若等于第三个部分则记录；其中肯定有重复，但可以先记录每一个满足的结果之后再减去重复的。

而且，可以知道m与n位数的乘积位数为m+n或m+n-1，所以若以i,j来标记0~8中的两个分割点，则该分割中j必取4：如果把0~i当成第一个数，i+1~j当成第二个数，j+1~8当成第三位数，则第一个数有i+1位，第二个数有j-i位，第三个数有8-j位，满足i+1+j-i=8-j或8-j+1，j=4或3.5 取整j只能等于4。所以第三个部分的数一定是个4位数。

全排列相关的代码在24题已经说过这里不再放出了，自己写全排列也好调用next_permutation函数也好都行。要回看的往这走：全排列详见24题。

这里只写写判断.判断可以先写个i为变量的函数 无非就是把三部分从数组中取出做成数：

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;

}

只要注意一下对应的位数并调用质数函数pow 

查看有无重复也不难，外部用一个数组储存所有的4位数，如果该4位数满足某个等式标记之就行了。最后主函数中直接数这个数组。

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位数除以2位数的真分数中，有4个分数满足去掉不同位的数字后分数值保持不变，比如49/98，去掉不同位的9后4/8=49/98，找到所有的4个分数，求出它们相乘约分后的分母。

即使在我现在做到的题中，这道的也算规模算非常小的了，也许可以手算？不过节能的我还是选择了遍历所有2位数除法然后判断...

判断函数：

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;

}

主函数中随便跑跑即可。

这样的分数为16/64=1/4,26/65=2/5,19/95=1/5,49/98=4/8=1/2,乘积为1/100

不得不说做欧拉计划的题还是很长见识的。

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.

找到所有满足本身等于其每个位置数字阶乘之和的数字之和。注意1！与2！不算在内。

先确定上界，注意到9999999>9!×7（7位数上界），而999999<9!×6，故上界为9999999

为了方便可以先用一个数组jie[10]保存0~9的阶乘；之后便是主函数中从11跑起跑到9999999，逐个判断过去；判断方法按照定义.check函数可以这样：

int sum=0,nx=n;

while(nx)

{

sum+=jie[nx%10];

nx/=10;

}

if(sum==n)return 1;

return 0;

主函数就懒得放了。跑出来只有2个数符合，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?

循环质数具有性质：数的任意全排列为质数，找到1000000以内的所有循环质数的个数。

看来这几道系列题都重心都在数本身与数的位上的数. 在c++里其实就是数组与数的互化；思路很清楚 筛一个质数表 检验每个质数的全排列。最好是再开个数组记录循环素数.但 我懒。

数组数，质数欧拉筛，全排列..好像以前都讲过了...不如这题就不放代码了吧 （手动[doge]

那么姑且说一下结果，注意个位数的2，3，5，7也要算上；2位数题干中放了；3位数从113开始，一直到最大的6位数999331.

总共有55个

ans:55

不知为何感觉这5题比上5题水了不少...

再次声明俺只提供部分的个人思考过程与关键算法.具体实现自己动手丰衣足食.不然俺寻思着您这过来抄个答案有啥意思呢.这么累的搬运个数据就能获得物质或精神上不菲的回报不成？

那么祝各位有所收获.无论是在数学知识抑或码风写法优化上

有缘再见.