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

观前声明：    

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

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

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

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

第26题：

Reciprocal cycles

Problem 26

A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 2 to 10 are given:

1/2= 0.5

1/3= 0.(3)

1/4= 0.25

1/5= 0.2

1/6= 0.1(6)

1/7= 0.(142857)

1/8= 0.125

1/9= 0.(1)

1/10= 0.1

Where 0.1(6) means 0.166666..., and has a 1-digit recurring cycle. It can be seen that 1/7 has a 6-digit recurring cycle.

Find the value of d < 1000 for which 1/d contains the longest recurring cycle in its decimal fraction part.

找到1000以内的正整数d使得1/d拥有多长的无限循环小数。

可以证明：

对于一个数，如果它的质因子仅有2，5，则1/d必没有循环小数；

所以对于一个数n，先把它的所有2，5因子除去得到nb，对于nb若能用最小长度为len的“999....”整除，则n或nb的循环小数个数为len。

例999999整除7，所以1/7的循环小数就是6。

实现起来也不难，先令被除数tem=9，如果不能整除nb，那么令tem=tem%nb*10+9（实际上这是在模拟除法，因为已经约去2，5使得nb不能整除2，5）

9/7=1...2    29/7=4...1   19/7=2...5  59/7=8...3  39/7=5...4   49%7=0  1/7的循环小数即为

0.(142857)  而上述过程重复了6次。

对应的2个函数：

int findbase(int n)

{

int i, base = n;

for (i = 0; base % 2 == 0; i++)

base /= 2;

for (i = 0; base % 5 == 0; i++)

base /= 5;

return base;

}

int cyclelength(int n)

{

int nb = findbase(n), tem = 9, count = 1;

if (nb == 1)return 0;

while (tem % nb != 0)

{

tem = tem % nb * 10 + 9;

count++;

}

return count;

}

ans:983   （1/983有982位循环小数）

第27题：

Quadratic primes

Problem 27

Euler discovered the remarkable quadratic formula:

n^2+n+41

It turns out that the formula will produce 40 primes for the consecutive integer values 0≤n≤39. However, when n=40,402+40+41=40(40+1)+41 is divisible by 41, and certainly when n=41,412+41+41 is clearly divisible by 41.

The incredible formula n^2-79n+1601 was discovered, which produces 80 primes for the consecutive values 0≤n≤79. The product of the coefficients, -79 and 1601, is -126479.

Considering quadratics of the form:

n^2+an+b, where |a|<1000 and |b|≤1000

where |n| is the modulus/absolute value of n

e.g. |11|=11 and |-4|=4

Find the product of the coefficients, a and b, for the quadratic expression that produces the maximum number of primes for consecutive values of n, starting with n=0.

渣翻一下：

欧拉发现取n从0到39代入方程n^2+n+41能够得到40个质数，n取40时n^2+n+41被41整除；

方程n^2-79n+1601 更是离谱，取从0到79能够生成80个质数

找到|a|<1000 且|b|≤1000的a和b使得它们形成的方程n^2+an+b能够得到最多的连续质数（取n从0到某个值），并求出ab

简单分析一下方程n^2+an+b，n取0的时候必须是个质数，所以b为-1000到1000内的素数，因为上面已经有1例生成了40个质数了，那么n取1的时候我们也可以考虑其为质数，所以a+b+1是质数，所以a+b是偶数，所以a是-999到999的偶数

缩小了点范围后就可以开始暴搜了，当然继续分析也可以进一步缩小范围.

关于质数和判断质数之类的函数及处理方法之前的题中也介绍过.就不多说了.有了判断在循环里检验每个独立的a,b形成的方程能生成多少个连续质数就行了。

比如数a，b的生成质数个数能这么写：

（其中已经跑过一遍筛子获得质数表了）

int facnum(int a, int b)

{

int n = 0, sum = 0;

while (1)

{

long long fn = n * n + a * n + b;

if (！prime[fn]) { sum++; n++; }

else break;

}

return sum;

}

主函数就两个for的事；虽然是暴搜，但规模小也不慢。

ans:a=-61,b=971,ab=-59231,（能生成71个质数）

第28题：

Number spiral diagonals

Problem 28

Starting with the number 1 and moving to the right in a clockwise direction a 5 by 5 spiral is formed as follows:

21 22 23 24 25
20  7  8  9 10
19  6  1  2 11
18  5  4  3 12
17 16 15 14 13

It can be verified that the sum of the numbers on the diagonals is 101.

What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral formed in the same way?

从1开始逆时针旋转扩大形成1个5×5矩阵，对角线元素之和为101，那么形成1001×1001矩阵对角线元素之和为？

小学找规律题.下一道！（雾）

不难发现 n×n阵右上角元素为n^2，从右下角到右上角四个顶点元素依次为n^2-3(n-1),n^2-2(n-1),n^2-(n-1),n^2，所以一个n×n环的4个元素和为4n^2-6(n-1)

遍历从3开始到1001的奇数环，求4n^2-6(n-1)的和。手算的话，取n=2k+1

4(2k+1)^2-6(2k)=16k^2+4k+4    k从1到500求和应该不会有人不会算吧..

1^2+2^2+...+n^2=n(n+1)(2n+1)/6  1+..+n=n(n+1)/2 就算不会证至少要记住a

8n(n+1)(2n+1)/3+2n(n+1)+4n取n=500

ans:669171001

第29题：

Distinct powers

Problem 29

Consider all integer combinations of ab for 2 ≤ a ≤ 5 and 2 ≤ b ≤ 5:

2^2=4, 2^3=8, 2^4=16, 2^5=32

3^2=9, 3^3=27, 3^4=81, 3^5=243

4^2=16, 4^3=64^4=256, 4^5=1024

5^2=25, 5^3=125, 5^4=625, 5^5=3125

If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:

4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

How many distinct terms are in the sequence generated by ab for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?

令 2 ≤ a ≤ 5 和 2 ≤ b ≤ 5，得到所有a^b，共有15个数字

那么令2 ≤ a ≤ 100 和 2 ≤ b ≤ 100则有多少个数字呢？

先说最蠢的思路： 算出所有 然后数.那么算要怎么算？都知道2^100是个大整数，又到了谁的拉跨时间？ 没错我们的c++

终于写到关于乘法的模拟了，事实上，我们计算多位数乘法时

如果令n1=a[s]a[s-1]a[s-2]a[s-3]...a[0]（比如123，a2=1,a1=2,a0=3），n2=bt...b0（比如234，...）

那么n3=n1*n2=c[p]c[p-1]c[p-2]...c0(这里假设ci还未进位)中，c[i+j]=a[0]*b[i+j]+a[1]*b[i+j-1]+...+a[i+j]*b[0]（实际上这就是我们手算多位数乘法的模拟，只是所有都先不进位而已）

比如123×234，c[0]=a[0]*b[0]=12,c[1]=a[0]*b[1]+a[1]*b[0]=9+8=17,c[2]=6+6+4=16,c[3]=4+3=7,c[4]=2,

从c[0]开始进位，得到n3=28782。

那么我们的大整数乘法就完成了，不过这里先写指数，a^b就是b个a相乘（a,b为整数），那么调用b次乘法就是指数.  因为2~100有99个数，所以所有的a^b的上限为9801个

我们用二维数组A[9802][]记录，A[n][]表示（n=(a-2)*99+b-1）a^b（唯一对应）的数组模拟储存。

如果A[n0][]表示第n0个指数，那么将a存储进B[]（相关代码见之前题中用过的的大整数加法）

不断让A，B相乘并改变A的储存情况 使用count计数：

while (count < b)

{

int C[10000] = { 0 }; count++;

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

C[i] = A[no][i];

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

{

int sum = 0;

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

sum += B[j] * C[i - j + 1];

A[no][i] = sum;

}

if (A[no][i - 1] != 0)A[no][0] = i - 1;

else A[no][0] = i - 2;

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

{

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

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

A[no][i] %= 10;

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

}

}

这就是基本的核心代码了.剩下的就是判断查重然后计数  自己写写不难。

至于另一种思路就是找到多少重复然后减去之 规模小分析起来不难（其实只是为了节能懒得分析 暴力能轻松跑为什么要脑子.） 这里我只想讲讲大整数乘法所以才专门用这种思路而已.

ans:9183

第30题：

Digit fifth powers

Problem 30

Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits:

1634 = 1^4 + 6^4 + 3^4 + 4^4

8208 = 8^4 + 2^4 + 0^4 + 8^4

9474 = 9^4 + 4^4 + 7^4 + 4^4

As 1 = 1^4 is not a sum it is not included.

The sum of these numbers is 1634 + 8208 + 9474 = 19316.

Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.

与自身每位上的数的4次方和相等的数只有3个1634，8208，9474

求出所有与自身每位上的数的5次方和相等的数的和。

检验一个数是不是满足这个情况很简单，但第一步要做的永远都是分析题目缩小范围。

若一个n位数满足，上界为n*9^5，我们随便带个判断，9位数的上界是9^6=531441，只有6位数，显然9位数太大了，往下找；8位数上界8*9^5=472392，还是太大；7位数：413343,继续；6位数：354294,也为6位数，满足了；

当然可以继续在小范围内进一步缩小，但我懒，所以上界就设置为999999，遍历2~999999检验判断即可；把数存进数组的方法用一个循环while 之前大整数模拟也用过很多次了

while(n)

{

n%10=A[len++]

n/=10;

}

或者为了方便，直接从2开始把2存进数组A[0]=1,A[1]=2,检验完后大整数加法加1继续检验，都是可以的。

ans:443839

那么 就到这里吧.有缘再见