定义：形如
x
2
−
d
y
2
=
1
x^2 - dy^2 = 1
x2−dy2=1(d>1,且d不是完全平方数) 要求第一类佩尔方程的解都是正整数解,也即
(
x
,
y
)
,
x
>
0
,
y
>
0
(x,y),x>0,y>0
(x,y),x>0,y>0
为什么要求d不是完全平方数呢？ 我们假设d是完全平方数 则
x
2
−
d
y
2
=
1
x^2 - dy^2 = 1
x2−dy2=1等价于
(
x
+
d
∗
y
)
(
x
−
d
∗
y
)
=
1
(x+\sqrt d*y)(x-\sqrt d*y) = 1
(x+d∗y)(x−d∗y)=1 所以它的解只有可能是(1,0),(-1,0)，不是正整数解。
为什么d>1呢?因为如果d<=1，解也不会是正整数解，自己证明试试看。
显然佩尔方程
x
2
−
d
y
2
=
1
x^2 - dy^2 = 1
x2−dy2=1有无数多个解，那么如何求最小的正整数解呢
我们把式子化简一下就变成了，
x
=
1
+
d
y
2
x=\sqrt{1+dy{2}}
x=1+dy2,我们从y=1开始枚举y，如果
1
+
d
y
2
\sqrt{1+dy{2}}
1+dy2是整数的话，此时的x,y就是最小的正整数，也就得到了最小正整数解
这里给出通解的迭代公式
x
n
=
x
n
−
1
x
1
+
d
y
n
−
1
y
1
x_n = x_{n-1}x_1 + dy_{n-1}y_1
xn=xn−1x1+dyn−1y1
y
n
=
x
n
−
1
y
1
+
y
n
−
1
x
1
y_n = x_{n-1}y_1 + y_{n-1}x_1
yn=xn−1y1+yn−1x1 这个通解公式怎么推导的呢？我们要知其然，而知其所以然
推导：我们令(x1,y1),(x2,y2)为方程的两个特解
x
1
2
−
d
y
1
2
=
1
x_1^2-dy_1^2=1
x12−dy12=1----①
x
2
2
−
d
y
2
2
=
1
x_2^2-dy_2^2=1
x22−dy22=1----② 两式想乘得到
(
x
1
2
−
d
y
1
2
)
∗
(
x
2
2
−
d
y
2
2
)
=
1
(x_1^2-dy_1^2)*(x_2^2-dy_2^2)=1
(x12−dy12)∗(x22−dy22)=1 展开得到
x
1
2
x
2
2
−
d
x
1
2
y
2
2
−
d
y
1
2
x
2
2
+
d
2
y
1
2
y
2
2
=
1
x_1^2x_2^2-dx_1^2y_2^2-dy_1^2x_2^2+d^2y_1^2y_2^2=1
x12x22−dx12y22−dy12x22+d2y12y22=1 ->
[
x
1
2
x
2
2
+
d
2
y
1
2
y
2
2
]
−
d
[
d
x
1
2
y
2
2
+
y
1
2
x
2
2
]
=
1
[x_1^2x_2^2+d^2y_1^2y_2^2]-d[dx_1^2y_2^2+y_1^2x_2^2]=1
[x12x22+d2y12y22]−d[dx12y22+y12x22]=1 ->
[
x
1
2
x
2
2
+
d
2
y
1
2
y
2
2
+
2
d
x
1
x
2
y
1
y
2
]
−
d
[
d
x
1
2
y
2
2
+
y
1
2
x
2
2
+
2
x
1
x
2
y
1
y
2
]
=
1
[x_1^2x_2^2+d^2y_1^2y_2^2+2dx_1x_2y_1y_2]-d[dx_1^2y_2^2+y_1^2x_2^2+2x_1x_2y_1y_2]=1
[x12x22+d2y12y22+2dx1x2y1y2]−d[dx12y22+y12x22+2x1x2y1y2]=1 ->
(
x
1
x
2
−
d
y
1
y
2
)
2
−
d
(
x
1
y
2
+
x
2
y
1
)
2
=
1
(x_1x_2-dy_1y_2)^2-d(x_1y_2+x_2y_1)^2=1
(x1x2−dy1y2)2−d(x1y2+x2y1)2=1 所以
x
3
=
x
2
x
1
+
d
y
2
y
1
,
y
3
=
x
2
y
1
+
x
1
y
2
x_3=x_2x_1+dy_2y_1,y_3=x_2y_1+x_1y_2
x3=x2x1+dy2y1,y3=x2y1+x1y2 我们把下标换为n就得到
x
n
=
x
n
−
1
x
1
+
d
y
n
−
1
y
1
x_n = x_{n-1}x_1 + dy_{n-1}y_1
xn=xn−1x1+dyn−1y1
y
n
=
x
n
−
1
y
1
+
y
n
−
1
x
1
y_n = x_{n-1}y_1 + y_{n-1}x_1
yn=xn−1y1+yn−1x1
这样的话我们只要知道第一个特解
(
x
1
,
y
1
)
(x1,y1)
(x1,y1)，和第n-1个特解
(
x
n
−
1
,
y
n
−
1
)
(x_{n-1},y_{n-1})
(xn−1,yn−1),就能够求出第n个解，但是很明现如果暴力求第n个解的话，时间复杂度是O(n),如果n很大的话就会超时，我们这时候可以用矩阵快速幂logn的复杂度来就快速求取，第n个解。
step2:根据迭代公式找到所有我们要找的解，也就是
x
n
=
x
n
−
1
x
1
+
d
y
n
−
1
y
1
x_n = x_{n-1}x_1 + dy_{n-1}y_1
xn=xn−1x1+dyn−1y1
y
n
=
x
n
−
1
y
1
+
y
n
−
1
x
1
y_n = x_{n-1}y_1 + y_{n-1}x_1
yn=xn−1y1+yn−1x1
[
x
n
y
n
]
\begin{bmatrix} x_n\\ y_n \end{bmatrix}
[xnyn]=
[
x
1
d
y
1
y
1
x
1
]
n
−
1
\begin{bmatrix} x_1&dy_1 \\ y_1&x_1 \end{bmatrix}^{n-1}
[x1y1dy1x1]n−1
[
x
1
y
1
]
\begin{bmatrix} x_1\\ y_1 \end{bmatrix}
[x1y1] 这样我们就可以用矩阵快速幂来求取方程的第n个解，时间复杂度是O(logn),矩阵快速幂就类似于普通的快速幂，只不过我们的底数是一个矩阵，而不是一个常数，如果不了解矩阵快速幂的，请出门右转(矩阵快速幂)。
Street Numbers 题目大意:找出n，m使得
1
+
2
+
3
+
.
.
.
.
+
(
n
−
1
)
=
(
n
+
1
)
+
(
n
+
2
)
.
.
.
.
+
m
1+2+3+....+(n-1)=(n+1)+(n+2)....+m
1+2+3+....+(n−1)=(n+1)+(n+2)....+m,输出前十个解(n,m)。每个数字占是个字符，向右对齐，且每一排升序排列。
分析：我们不难发现，等式的左右都是一个等差数列，那么我们处理一下就可以得到这样一个等式，
(
2
m
+
1
)
2
−
8
n
2
=
1
(2m+1)^2-8n^2=1
(2m+1)2−8n2=1,我们令
x
=
(
2
m
+
1
)
,
y
=
n
,
d
=
8
x=(2m+1),y=n,d=8
x=(2m+1),y=n,d=8,这不就是一个裸的佩尔方程吗？我们只需要找到x，y就能找到m，n。
定义:形如
x
2
−
d
y
2
=
k
x^2 - dy^2 = k
x2−dy2=k的方程叫做第二类佩恩方程 第二类佩尔方程可以看成是第一类佩尔的拓展，也相对复杂一点
解第二类佩恩方程，需要用到第一类方程的解。
推导： 我们假设
x
2
−
d
y
2
=
k
−
−
−
−
−
①
x^2 - dy^2 = k-----①
x2−dy2=k−−−−−①的一个特解为
p
，
q
p，q
p，q 设
x
2
−
d
y
2
=
1
−
−
−
−
−
②
x^2 - dy^2 = 1-----②
x2−dy2=1−−−−−②的正整数解为
x
1
,
y
1
x1,y1
x1,y1，①×②式就可以得到下面式子。 ->
(
p
2
−
d
q
2
)
∗
(
x
1
2
−
d
y
1
2
)
=
k
(p^2-dq^2)*(x_1^2-dy_1^2)=k
(p2−dq2)∗(x12−dy12)=k ->
(
p
x
1
±
d
q
y
1
)
2
−
d
(
p
y
1
±
q
x
1
)
2
=
k
(px_1\pm dqy_1)^2-d(py_1\pm qx_1)^2 =k
(px1±dqy1)2−d(py1±qx1)2=k 所以通解为,
x
=
p
x
1
±
d
q
y
1
x=px_1\pm dqy_1
x=px1±dqy1,
y
=
p
y
1
±
q
x
1
y=py_1\pm qx_1
y=py1±qx1 我们假设②式中d=2，那么
x
2
−
2
y
2
=
1
x^2-2y^2=1
x2−2y2=1，解得最小正整数解是
x
1
=
3
,
y
1
=
2
x_1=3,y_1=2
x1=3,y1=2,那么①式的解就是
x
n
=
3
x
n
−
1
±
4
y
n
−
1
x_n=3x_{n-1}\pm 4y_{n-1}
xn=3xn−1±4yn−1,
y
n
=
2
x
n
−
1
±
3
y
n
−
1
y_n=2x_{n-1}\pm 3y_{n-1}
yn=2xn−1±3yn−1。
遇到第二类佩尔方程也不用害怕，只需要和第一类佩尔方程联系起来求出通解即可。我们更具第二类佩尔方程的通解，
x
=
p
x
1
+
d
q
y
1
x=px_1+dqy_1
x=px1+dqy1,
y
=
p
y
1
+
q
x
1
y=py_1+ qx_1
y=py1+qx1，可以转化为矩阵乘法的形式
[
x
n
y
n
]
\begin{bmatrix} x_n\\ y_n \end{bmatrix}
[xnyn]=
[
p
d
q
q
p
]
n
−
1
\begin{bmatrix} p &dq \\ q&p \end{bmatrix}^{n-1}
[pqdqp]n−1
[
x
1
y
1
]
\begin{bmatrix} x_{1}\\ y_{1} \end{bmatrix}
[x1y1],这样就方便用矩阵快速幂求第k个解
