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

观前声明：      

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

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

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

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

前排：本期连分数题3连. 当时我被乱杀.

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?

任意非平方数N的平方根可以进行无限连分数展开：

并且这个无限展开是有特定循环周期的，比如根号23：

除了第一个4外，根号23具有长度为4的循环节，写成：√23=[4;(1,3,1,8)]

13内的非平方数只有根号13具有奇循环节，问10000以内的非平方数N 的平方根有多少个奇数循环节？

要做清楚这道题，我们需要先了解展开的机制，题设已经拿根号23举例了

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

这其实是在拿整数去逼近根号23，最接近但又小于根号23的整数是4

所以a0=4，然后为了继续逼近√23-4，先写成1/（分母有理化的形式）

1/（）  括号内就是(√23+4)/7    最接近它的整数是1  所以a1=1

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

最后就能得到

知道这个机制之后就能尝试实现了：

令p,q为整型变量  开始时先令double型的k=根号n   （k是每次要逼近的东西    q之后要作为除去的分母，p之后作为分子上要加的整数，先令p=(int)k 即为a0（对应cnt=0,a[cnt++]=p），q=1）

以√23的第一次循环为例（实际上在草稿纸上写写就能明白了）：

对于√23 第一个分母是7，其实就是(23-4*4)/1，也就是 

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

更新k为(√n+p)/q   在23的第一次循环中这里就是(√23+4) /7  

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

最接近k的下位整数按顺序存在数组里（√23的第一次循环(int)k为1）：

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

更新分子p（√23的第一次循环这里就是  a1*7-4=3）：

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

循环停止条件fabs(k - a[cnt - 1] - st) > 10e-10   st是√n-a0  就是第一个待逼近数的小数部分，而k-a[cnt-1]就是当前在逼近值的小数部分  

在图

这里可以发现a0和a4的待逼近数相同 所以只要设定一个合理的精度 2者差在精度内就可默认我们已经得到了一个循环了（因为double 求根什么的难免有误差）

在主函数中跑10000以内的非平方数，计数所有循环节为奇数的数即可。

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.

（连分数2杀）

无理数e的连分数展开用上题的写法能写成：e=[2;1,2,1,1,4,1,1,6,1,...,1,2k,1,...].

若将此有限分数写成序列：

第一项是2，第二项是2+1/a1=3，第三项是2+1/(a1+1/(a2))=8/3....

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

排列出来的前10项是：

第10项的分子的每位数相加的和为1+4+5+7=17

那么第100项每位数相加的和是多少？

怎么说呢 这道题虽然有连分数的背景  理解也是要用连分数相关知识来理解

但本质上 我觉得这是找规律就能解决的数列题......

这个可以直接观察得到 令分子为p(n),分母为q(n)

标记序列中每个数的lian值为1 2 1 1 4 1 1 6 1....1 2k 1... 

令f(n)=pn/qn,那么当n=3,6,9...时pn=(p(n-2))+(2n/3)*(p(n-1)),qn=(q(n-2))+(2n/3)*(q(n-1));

n不为3的倍数时因为lian值为1，所以是pn=1*p(n-1)+p(n-2),qn=1*q(n-1)+q(n-2)

这里有个很重要的结论，就是连分数展开得到的分数序列的递推式：

令分子为p(n),分母为q(n),连分数展开得到的数组为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)

直接看出来也行.

照这个递推式迭代就行，因为c++比较拉跨 所以要用大整数的加法和乘法.

大整数都老熟人了 直接过撒.

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是平方数时一般默认无解

D 取 {2, 3, 5, 6, 7}这些值时，方程的最小整数解x分别为：3，2，9，5，8

可见D<=7时 D=5有最大的最小整数解x=9

D<=1000时找到D的值使x有最大的最小整数解。

第一个反应是对于一个D，从2开始找x，如果x*x/D是一个完全平方数，那么就找到了最小的x

可惜这一套精度不够，于是又想写大整数，根据x^2=Dy^2+1,y最小时x有最小值，然而要检验大整数是否为平方数太困难了，或者说写起来太麻烦，折半查也要nlogn，遂放弃。

但是   我为什么要说这是 连分数3杀呢？

这时突然想到，上两题就是提示，根号D可以约等于x/y，将根号D的连分数展开得到序列，那么如果某个x/y满足丢番图方程，即是最小值。

利用64题的checkjie函数求a(n)(在下段代码中为函数pannin)；

利用65题给出的结论求分数序列：

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++来说直接求是求不出的..（答案对应的x有近40位）

所以要用大整数，根据上段代码的思路改编成大整数：

结构体Dx存放所有的D及之后的分数序列的分子分母还有连分数展开节点值;

sum函数为大整数加法，mutiply函数为大整数乘法;

pannin函数求出根号D的连分数展开节值，并储存进数组a[]中

getpn与getqn函数为在当前为n时进行一次65题中的结论的迭代;

checkpqnD函数求出根号D的连分数展开分子序列，并在获得最小值x后停止迭代;

因为获得了1000以内非平方数D对应的最小x值（存在pn中）后还要比较大小

fight函数执行此功能

主函数调用上述跑就行了（记得当时写的有点神志不清了）

D=661时 最小的x：16421658242965910275055840472270471049

（这题的代码写的真的累...我被乱杀） 

ans：661

不好意思 原本该是呈现出   66题居然统一了64和65题的算法  这种神奇又伴有开心的体验的

但我自己的66题写了段又臭又长毫无美感的代码 而且至今不知道c++怎么才能更简洁的完成之

连分数3杀的这三道题难度分别为 20% 15% 25% 算是100题内质量算高的有关联的题了.

之后会失踪一段时间.

有缘更新后续.