關(guān)于啥是Project Euler 詳見 https://projecteuler.net/about???

觀前聲明：? ??

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

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

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

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以內(nèi)的正整數(shù)d使得1/d擁有多長的無限循環(huán)小數(shù)。

可以證明：

對于一個數(shù)，如果它的質(zhì)因子僅有2，5，則1/d必沒有循環(huán)小數(shù)；

所以對于一個數(shù)n，先把它的所有2，5因子除去得到nb，對于nb若能用最小長度為len的“999....”整除，則n或nb的循環(huán)小數(shù)個數(shù)為len。

例999999整除7，所以1/7的循環(huán)小數(shù)就是6。

實現(xiàn)起來也不難，先令被除數(shù)tem=9，如果不能整除nb，那么令tem=tem%nb*10+9（實際上這是在模擬除法，因為已經(jīng)約去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的循環(huán)小數(shù)即為

0.(142857)? 而上述過程重復(fù)了6次。

對應(yīng)的2個函數(shù)：

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位循環(huán)小數(shù)）

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

渣翻一下：

歐拉發(fā)現(xiàn)取n從0到39代入方程n^2+n+41能夠得到40個質(zhì)數(shù)，n取40時n^2+n+41被41整除；

方程n^2-79n+1601 更是離譜，取從0到79能夠生成80個質(zhì)數(shù)

找到|a|<1000 且|b|≤1000的a和b使得它們形成的方程n^2+an+b能夠得到最多的連續(xù)質(zhì)數(shù)（取n從0到某個值），并求出ab

簡單分析一下方程n^2+an+b，n取0的時候必須是個質(zhì)數(shù)，所以b為-1000到1000內(nèi)的素數(shù)，因為上面已經(jīng)有1例生成了40個質(zhì)數(shù)了，那么n取1的時候我們也可以考慮其為質(zhì)數(shù)，所以a+b+1是質(zhì)數(shù)，所以a+b是偶數(shù)，所以a是-999到999的偶數(shù)

縮小了點范圍后就可以開始暴搜了，當然繼續(xù)分析也可以進一步縮小范圍.

關(guān)于質(zhì)數(shù)和判斷質(zhì)數(shù)之類的函數(shù)及處理方法之前的題中也介紹過.就不多說了.有了判斷在循環(huán)里檢驗每個獨立的a,b形成的方程能生成多少個連續(xù)質(zhì)數(shù)就行了。

比如數(shù)a，b的生成質(zhì)數(shù)個數(shù)能這么寫：

（其中已經(jīng)跑過一遍篩子獲得質(zhì)數(shù)表了）

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;

}

主函數(shù)就兩個for的事；雖然是暴搜，但規(guī)模小也不慢。

ans:a=-61,b=971,ab=-59231,（能生成71個質(zhì)數(shù)）

第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開始逆時針旋轉(zhuǎn)擴大形成1個5×5矩陣，對角線元素之和為101，那么形成1001×1001矩陣對角線元素之和為？

小學找規(guī)律題.下一道?。F）

不難發(fā)現(xiàn) n×n陣右上角元素為n^2，從右下角到右上角四個頂點元素依次為n^2-3(n-1),n^2-2(n-1),n^2-(n-1),n^2，所以一個n×n環(huán)的4個元素和為4n^2-6(n-1)

遍歷從3開始到1001的奇數(shù)環(huán)，求4n^2-6(n-1)的和。手算的話，取n=2k+1

4(2k+1)^2-6(2k)=16k^2+4k+4? ? k從1到500求和應(yīng)該不會有人不會算吧..

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個數(shù)字

那么令2 ≤?a?≤ 100?和?2 ≤?b?≤ 100則有多少個數(shù)字呢？

先說最蠢的思路： 算出所有 然后數(shù).那么算要怎么算？都知道2^100是個大整數(shù)，又到了誰的拉跨時間？ 沒錯我們的c++

終于寫到關(guān)于乘法的模擬了，事實上，我們計算多位數(shù)乘法時

如果令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(這里假設(shè)ci還未進位)中，c[i+j]=a[0]*b[i+j]+a[1]*b[i+j-1]+...+a[i+j]*b[0]（實際上這就是我們手算多位數(shù)乘法的模擬，只是所有都先不進位而已）

比如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。

那么我們的大整數(shù)乘法就完成了，不過這里先寫指數(shù)，a^b就是b個a相乘（a,b為整數(shù)），那么調(diào)用b次乘法就是指數(shù).? 因為2~100有99個數(shù)，所以所有的a^b的上限為9801個

我們用二維數(shù)組A[9802][]記錄，A[n][]表示（n=(a-2)*99+b-1）a^b（唯一對應(yīng)）的數(shù)組模擬儲存。

如果A[n0][]表示第n0個指數(shù)，那么將a存儲進B[]（相關(guān)代碼見之前題中用過的的大整數(shù)加法）

不斷讓A，B相乘并改變A的儲存情況 使用count計數(shù)：

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]);

}

}

這就是基本的核心代碼了.剩下的就是判斷查重然后計數(shù)? 自己寫寫不難。

至于另一種思路就是找到多少重復(fù)然后減去之 規(guī)模小分析起來不難（其實只是為了節(jié)能懶得分析 暴力能輕松跑為什么要腦子.） 這里我只想講講大整數(shù)乘法所以才專門用這種思路而已.

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.

與自身每位上的數(shù)的4次方和相等的數(shù)只有3個1634，8208，9474

求出所有與自身每位上的數(shù)的5次方和相等的數(shù)的和。

檢驗一個數(shù)是不是滿足這個情況很簡單，但第一步要做的永遠都是分析題目縮小范圍。

若一個n位數(shù)滿足，上界為n*9^5，我們隨便帶個判斷，9位數(shù)的上界是9^6=531441，只有6位數(shù)，顯然9位數(shù)太大了，往下找；8位數(shù)上界8*9^5=472392，還是太大；7位數(shù)：413343,繼續(xù)；6位數(shù)：354294,也為6位數(shù)，滿足了；

當然可以繼續(xù)在小范圍內(nèi)進一步縮小，但我懶，所以上界就設(shè)置為999999，遍歷2~999999檢驗判斷即可；把數(shù)存進數(shù)組的方法用一個循環(huán)while 之前大整數(shù)模擬也用過很多次了

while(n)

{

n%10=A[len++]

n/=10;

}

或者為了方便，直接從2開始把2存進數(shù)組A[0]=1,A[1]=2,檢驗完后大整數(shù)加法加1繼續(xù)檢驗，都是可以的。

ans:443839

那么 就到這里吧.有緣再見