背景

对于一个\(x^2-dy^2=1\)的方程进行求解

这里的解为整数

其中\(d\)已知

解法

若d为完全平方数

\(x^2-(\sqrt dy)^2=1\)

\((x+\sqrt dy)(x-\sqrt d y)=1\)

因为我们要求的解为正整数，并且\(d\)也为正整数

所以\((x+\sqrt d y)\)和\((x-\sqrt dy)\)都为整数

\(\begin{cases}x+\sqrt dy=1\\x-\sqrt dy=1\end{cases}\)

或者

\(\begin{cases}x+\sqrt dy=-1\\x-\sqrt dy=-1\end{cases}\)

其中两个方程的解法一样，这里只对其中一种进行讨论

对于答案为\(1\)

将两个式子加起来，可以得到

\(\begin{cases}x=1\\y=0\end{cases}\)

或者

\(\begin{cases}x=-1\\y=0\end{cases}\)

若d不为完全平方数

引理

\(\begin{cases}x_1^2-dy_1^2=1\\x_2^2-dy_2^2=1\end{cases}\)

\((x_1^2-dy_1^2)(x_2^2-dy_2^2)=1\)

\(x_1^2x_2^2-dx_2^2y_1^2-dx_1^2y_2^2+d^2y_1^2y_2^2=1\)

\(((x_1x_2)^2+(dy_1y_2)^2)-d((x_1y_2)^2+(x_2y_1)^2)=1\)

\(((x_1x_2)^2+2dx_1x_2y_1y_2+(dy_1y_2)^2)-d((x_1y_2)^2+2x_1x_2y_1y_2+(x_2y_1)^2)=1\)

\((x_1x_2+dy_1y_2)^2-d(x_1y_2+x_2y_1)^2=1\)

所以\((x_1x_2+dy_1y_2,x_1y_2+x_2y_1)\)也为佩尔方程的一组解

注意这个式子对于\(x_1==x_2,y_1==y_2\)的时候一样成立

递推

这里讨论的解均为正整数

假设我们已经知道最小的一组解\((x_1,y_1),(x_1\ge0,y_1\ge0)\)

\(y_1=\sqrt{\frac{x_1^2-1}{d}}\)

很明显，对于\(x_1\)最小的时候，\(y_1\)也是最小的

考虑上面解的形式$(x_1x_2+dy_1y_2,x_1y_2+x_2y_1) $

我们假设\((x_i,y_i)\)为佩尔方程的第\(i\)小解

即\((x_1x_i+dy_1y_i,x_1y_i+x_iy_1)\)

首先对于\((x_i,y_i),d\)是固定的

也就用上面的引理推出来的解的大小与\(x_1,y_1\)相关

注意到我们讨论的解为正整数

推出来的解一定是随着\(x_1,y_1\)的增大而增大的

所以\(\begin{cases}x_{i+1}=x_1x_i+dy_1y_i\\y_{i+1}=x_1y_i+x_iy_1\end{cases}\)

很明显这个递推式是可以用矩阵快速幂优化的

\(\begin{bmatrix}x_{i+1}\\y_{i+1}\end{bmatrix}=\begin{bmatrix}x_1\\y_1\end{bmatrix}\begin{bmatrix}x_1,dy_1\\y_1,x_1\end{bmatrix}^i\)

最小解

根据实验证明，大多数题目的最小解都很小

所以直接暴力！！！

代码

咕咕咕