佩尔pell方程学习笔记

Posted on | In , , ,

去年已知的区域赛中pell方程已经考了两次

定义

  • 不定方程具有这样的形式：$x^2-dy^2=1$
  • 显然当n是平方数的时候，方程只有解$(\pm1,0)$

pell方程的解

  • 设$(x_1,x_2)，(y_1,y_2)$是 $pell$ 方程的两个解

  • 则有$\left{\begin{matrix}
    x_1^2-dy_1^2=1 \
    x_2^2-dy_2^2=1
    \end{matrix}\right.$

  • 两式子相乘得$(x_1^2-dy_1^2)·(x_2^2-dy_2^2=1)=1$，化简可得$(x_1x_2+ny_1y_2)^2-n(x_1y_2+x_2y_1)^2=1$

  • 故$\left{\begin{matrix}
    x_3=x_2x_1+dy_1y_2 \
    y_3=x_2y_1+ y_2x_1
    \end{matrix}\right.$

  • 可得通解$\left{\begin{matrix}
    x_n=x_{n-1}x_1+dy_{n-1}y_1 \
    y_n=x_{n-1}y_1+ y_{n-1}x_1
    \end{matrix}\right.$

  • $\begin{pmatrix}x_n\y_n\end{pmatrix}$=$\begin{pmatrix}
    x_1 & dy_1 \
    y_1 & x_1
    \end{pmatrix}^{n-1}$ $\begin{pmatrix}
    x_1\
    y_1
    \end{pmatrix}$

  • 所以得到最小特解$(x_1,y_1)$可以利用矩阵快速幂$\log$推出所有的整数解

求pell方程特解

暴力求解

1
2
3
4
5
6
7
8
void serach(int &x, int &y, int d){
    y=1;
    while(1){
        x=1LL*sqrt(d*y*y+1);
        if(x*x-d*y*y==1) break;
        y++;
    }
}

连分数法

可以参考lzy聚聚博客中关于连分数法的讲解