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

觀前聲明：? ? ??

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

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

3. 帶著惡意，抬杠者...俺也噴不過您，也不能拿您咋樣...畢竟這只是我個(gè)人興趣使然的行為或者說是學(xué)習(xí)記錄分享。?（說是記錄，但因?yàn)槭窃缦葘懙乃云鋵?shí)是在各種意義上公開處刑和吐槽自己 并嘗試補(bǔ)救優(yōu)化）

4. 語言是c++，用的VS平臺

前排：本期連分?jǐn)?shù)題3連. 當(dāng)時(shí)我被亂殺.

Odd period square roots

Problem 64

All square roots are periodic when written as continued fractions and can be written in the form:

For example, let us consider?√23:

If we continue we would get the following expansion:

The process can be summarised as follows:

It can be seen that the sequence is repeating. For conciseness, we use the notation

√23=[4;(1,3,1,8)], to indicate that the block (1,3,1,8) repeats indefinitely.

The first ten continued fraction representations of (irrational) square roots are:

Exactly four continued fractions, for?N≤13, have an odd period.

How many continued fractions for?N≤10000?have an odd period?

任意非平方數(shù)N的平方根可以進(jìn)行無限連分?jǐn)?shù)展開：

并且這個(gè)無限展開是有特定循環(huán)周期的，比如根號23：

除了第一個(gè)4外，根號23具有長度為4的循環(huán)節(jié)，寫成：√23=[4;(1,3,1,8)]

13內(nèi)的非平方數(shù)只有根號13具有奇循環(huán)節(jié)，問10000以內(nèi)的非平方數(shù)N 的平方根有多少個(gè)奇數(shù)循環(huán)節(jié)？

要做清楚這道題，我們需要先了解展開的機(jī)制，題設(shè)已經(jīng)拿根號23舉例了

我反正看了好久才看明白..

這其實(shí)是在拿整數(shù)去逼近根號23，最接近但又小于根號23的整數(shù)是4

所以a0=4，然后為了繼續(xù)逼近√23-4，先寫成1/（分母有理化的形式）

1/（）? 括號內(nèi)就是(√23+4)/7? ? 最接近它的整數(shù)是1? 所以a1=1

然后繼續(xù)逼近(√23+4)/7? -1=(√23-3)/7? ?化成1/（分母有理化的形式）....

最后就能得到

知道這個(gè)機(jī)制之后就能嘗試實(shí)現(xiàn)了：

令p,q為整型變量? 開始時(shí)先令double型的k=根號n? ?（k是每次要逼近的東西? ? q之后要作為除去的分母，p之后作為分子上要加的整數(shù)，先令p=(int)k 即為a0（對應(yīng)cnt=0,a[cnt++]=p），q=1）

以√23的第一次循環(huán)為例（實(shí)際上在草稿紙上寫寫就能明白了）：

對于√23 第一個(gè)分母是7，其實(shí)就是(23-4*4)/1，也就是?

q = (n - p * p) / q;

更新k為(√n+p)/q? ?在23的第一次循環(huán)中這里就是(√23+4)?/7??

k = (sqrt((double)n) + p) / q;

最接近k的下位整數(shù)按順序存在數(shù)組里（√23的第一次循環(huán)(int)k為1）：

a[cnt++] = (int)k;

更新分子p（√23的第一次循環(huán)這里就是? a1*7-4=3）：

p = a[cnt - 1] * q - p;

循環(huán)停止條件fabs(k - a[cnt - 1] - st) > 10e-10? ?st是√n-a0? 就是第一個(gè)待逼近數(shù)的小數(shù)部分，而k-a[cnt-1]就是當(dāng)前在逼近值的小數(shù)部分??

在圖

這里可以發(fā)現(xiàn)a0和a4的待逼近數(shù)相同 所以只要設(shè)定一個(gè)合理的精度 2者差在精度內(nèi)就可默認(rèn)我們已經(jīng)得到了一個(gè)循環(huán)了（因?yàn)閐ouble 求根什么的難免有誤差）

在主函數(shù)中跑10000以內(nèi)的非平方數(shù)，計(jì)數(shù)所有循環(huán)節(jié)為奇數(shù)的數(shù)即可。

ans：1322

Convergents of e

Problem 65

The square root of 2 can be written as an infinite continued fraction.

The infinite continued fraction can be written,?√2=[1;(2)],?(2)?indicates that 2 repeats?ad infinitum. In a similar way,?√23=[4;(1,3,1,8)].

It turns out that the sequence of partial values of continued fractions for square roots provide the best rational approximations. Let us consider the convergents for?√2.

Hence the sequence of the first ten convergents for?√2?are:

What is most surprising is that the important mathematical constant,
e=[2;1,2,1,1,4,1,1,6,1,...,1,2k,1,...].

The first ten terms in the sequence of convergents for?e?are:

The sum of digits in the numerator of the 10th?convergent is?1+4+5+7=17.

Find the sum of digits in the numerator of the 100th?convergent of the continued fraction for?e.

（連分?jǐn)?shù)2殺）

無理數(shù)e的連分?jǐn)?shù)展開用上題的寫法能寫成：e=[2;1,2,1,1,4,1,1,6,1,...,1,2k,1,...].

若將此有限分?jǐn)?shù)寫成序列：

第一項(xiàng)是2，第二項(xiàng)是2+1/a1=3，第三項(xiàng)是2+1/(a1+1/(a2))=8/3....

an見e=[2;1,2,1,1,4,1,1,6,1,...,1,2k,1,...].

排列出來的前10項(xiàng)是：

第10項(xiàng)的分子的每位數(shù)相加的和為1+4+5+7=17

那么第100項(xiàng)每位數(shù)相加的和是多少？

怎么說呢 這道題雖然有連分?jǐn)?shù)的背景? 理解也是要用連分?jǐn)?shù)相關(guān)知識來理解

但本質(zhì)上 我覺得這是找規(guī)律就能解決的數(shù)列題......

這個(gè)可以直接觀察得到 令分子為p(n),分母為q(n)

標(biāo)記序列中每個(gè)數(shù)的lian值為1 2 1 1 4 1 1 6 1....1 2k 1...?

令f(n)=pn/qn,那么當(dāng)n=3,6,9...時(shí)pn=(p(n-2))+(2n/3)*(p(n-1)),qn=(q(n-2))+(2n/3)*(q(n-1));

n不為3的倍數(shù)時(shí)因?yàn)閘ian值為1，所以是pn=1*p(n-1)+p(n-2),qn=1*q(n-1)+q(n-2)

這里有個(gè)很重要的結(jié)論，就是連分?jǐn)?shù)展開得到的分?jǐn)?shù)序列的遞推式：

令分子為p(n),分母為q(n),連分?jǐn)?shù)展開得到的數(shù)組為a(n)

p(0)=a(0)，p(1)=a(0)*a(1)+1

q(0)=1,q(1)=a(1)

p(n)=a(n)p(n-1)+p(n-2)

q(n)=a(n)q(n-1)+q(n-2)

直接看出來也行.

照這個(gè)遞推式迭代就行，因?yàn)閏++比較拉跨 所以要用大整數(shù)的加法和乘法.

大整數(shù)都老熟人了 直接過撒.

ans：272

Diophantine equation

Problem 66

Consider quadratic Diophantine equations of the form:

x^2?– Dy^2?= 1

For example, when D=13, the minimal solution in?x?is 6492?– 13×1802?= 1.

It can be assumed that there are no solutions in positive integers when D is square.

By finding minimal solutions in?x?for D = {2, 3, 5, 6, 7}, we obtain the following:

3^2?– 2×2^2?= 1
2^2?– 3×1^2?= 1
9^2?– 5×4^2?= 1
5^2?– 6×2^2?= 1
8^2?– 7×3^2?= 1

Hence, by considering minimal solutions in?x?for D ≤ 7, the largest?x?is obtained when D=5.

Find the value of D ≤ 1000 in minimal solutions of?x?for which the largest value of?x?is obtained.

對于丟番圖方程：? ? ?x^2?– Dy^2?= 1

D是平方數(shù)時(shí)一般默認(rèn)無解

D 取?{2, 3, 5, 6, 7}這些值時(shí)，方程的最小整數(shù)解x分別為：3，2，9，5，8

可見D<=7時(shí) D=5有最大的最小整數(shù)解x=9

D<=1000時(shí)找到D的值使x有最大的最小整數(shù)解。

第一個(gè)反應(yīng)是對于一個(gè)D，從2開始找x，如果x*x/D是一個(gè)完全平方數(shù)，那么就找到了最小的x

可惜這一套精度不夠，于是又想寫大整數(shù)，根據(jù)x^2=Dy^2+1,y最小時(shí)x有最小值，然而要檢驗(yàn)大整數(shù)是否為平方數(shù)太困難了，或者說寫起來太麻煩，折半查也要nlogn，遂放棄。

但是? ?我為什么要說這是 連分?jǐn)?shù)3殺呢？

這時(shí)突然想到，上兩題就是提示，根號D可以約等于x/y，將根號D的連分?jǐn)?shù)展開得到序列，那么如果某個(gè)x/y滿足丟番圖方程，即是最小值。

利用64題的checkjie函數(shù)求a(n)(在下段代碼中為函數(shù)pannin)；

利用65題給出的結(jié)論求分?jǐn)?shù)序列：

int checkD(int D)

{

? ? int a[1000] = { 0 };

? ? int lens = pannin(D, a);

? ? int p[100] = { 0 }, q[100] = { 0 };

? ? p[0] = a[0]; p[1] = a[0] * a[1] + 1; q[0] = 1; q[1] = a[1];

? ? int n = 0;

? ? if (p[n] * p[n] - 1 == q[n] * q[n] * D)return p[n];

? ? else n++;

? ? while (p[n] * p[n] - 1 != q[n] * q[n] * D)

? ? {

? ? ? ? n++;

? ? ? ? if (n % lens != 0)

? ? ? ? {

? ? ? ? ? ? p[n] = a[n % lens] * p[n - 1] + p[n - 2];

? ? ? ? ? ? q[n] = a[n % lens] * q[n - 1] + q[n - 2];

? ? ? ? }

? ? ? ? else

? ? ? ? {

? ? ? ? ? ? p[n] = a[lens] * p[n - 1] + p[n - 2];

? ? ? ? ? ? q[n] = a[lens] * q[n - 1] + q[n - 2];

? ? ? ? }

? ? }

? ? return p[n];

}

很可惜對于拉跨的c++來說直接求是求不出的..（答案對應(yīng)的x有近40位）

所以要用大整數(shù)，根據(jù)上段代碼的思路改編成大整數(shù)：

結(jié)構(gòu)體Dx存放所有的D及之后的分?jǐn)?shù)序列的分子分母還有連分?jǐn)?shù)展開節(jié)點(diǎn)值;

sum函數(shù)為大整數(shù)加法，mutiply函數(shù)為大整數(shù)乘法;

pannin函數(shù)求出根號D的連分?jǐn)?shù)展開節(jié)值，并儲存進(jìn)數(shù)組a[]中

getpn與getqn函數(shù)為在當(dāng)前為n時(shí)進(jìn)行一次65題中的結(jié)論的迭代;

checkpqnD函數(shù)求出根號D的連分?jǐn)?shù)展開分子序列，并在獲得最小值x后停止迭代;

因?yàn)楂@得了1000以內(nèi)非平方數(shù)D對應(yīng)的最小x值（存在pn中）后還要比較大小

fight函數(shù)執(zhí)行此功能

主函數(shù)調(diào)用上述跑就行了（記得當(dāng)時(shí)寫的有點(diǎn)神志不清了）

D=661時(shí) 最小的x：16421658242965910275055840472270471049

（這題的代碼寫的真的累...我被亂殺）?

ans：661

不好意思 原本該是呈現(xiàn)出? ?66題居然統(tǒng)一了64和65題的算法? 這種神奇又伴有開心的體驗(yàn)的

但我自己的66題寫了段又臭又長毫無美感的代碼 而且至今不知道c++怎么才能更簡潔的完成之

連分?jǐn)?shù)3殺的這三道題難度分別為 20% 15% 25% 算是100題內(nèi)質(zhì)量算高的有關(guān)聯(lián)的題了.

之后會失蹤一段時(shí)間.

有緣更新后續(xù).