题解：P14551 【模板】Pell 方程

· · 题解

题目传送门

update: 2026.1.31 修改三角函数的笔误。

:::info[前言] Pell 方程，看着很难，实际搞懂了原理还是很简单的。

本篇题解讲述关于 Pell 方程的详细解法。 :::

引入

$$ \sqrt{2}=\vert 1+i \vert $$ $$ \sqrt{2}=\sec45\degree $$ $$ \sqrt{2}=\sum_{k=0}^{\infty} \binom{\frac{1}{2}}{k} $$ 但要说里面最有趣的那一个，应该就是这个连分数。 $$ \sqrt{2}=1+\frac{1}{2+\frac{1}{2+\frac{1}{2+\frac{1}{2+\frac{1}{\dots}}}}} $$ 然而，我们并不能通过这个连分数直接计算得到 $\sqrt{2}$，因为有的时候我们会得到 $\pm\sqrt{2}$ 两个答案。 $$ \begin{align*} \sqrt{2} &=1+(\sqrt{2}-1)\\ &=1+\frac{(\sqrt{2}-1)(\sqrt{2}+1)}{(\sqrt{2}+1)}\\ &=1+\frac{1}{1+\sqrt{2}}\\ &=1+\frac{1}{2+\frac{1}{1+\sqrt{2}}}\\ &=1+\frac{1}{2+\frac{1}{2+\frac{1}{1+\sqrt{2}}}}\\ &=1+\frac{1}{2+\frac{1}{2+\frac{1}{2+\frac{1}{2+\frac{1}{\dots}}}}} \end{align*} $$ $$ \begin{align*} -\sqrt{2} &=1+(-\sqrt{2}-1)\\ &=1+\frac{(-\sqrt{2}-1)(-\sqrt{2}+1)}{(-\sqrt{2}+1)}\\ &=1+\frac{1}{1-\sqrt{2}}\\ &=1+\frac{1}{2+\frac{1}{1-\sqrt{2}}}\\ &=1+\frac{1}{2+\frac{1}{2+\frac{1}{1-\sqrt{2}}}}\\ &=1+\frac{1}{2+\frac{1}{2+\frac{1}{2+\frac{1}{2+\frac{1}{\dots}}}}} \end{align*} $$ 或者： $$ \begin{align*} x&=1+\frac{1}{1+x}\\ \Rightarrow x&=\pm\sqrt{2} \end{align*} $$ 想要得到 $\sqrt{2}$，我们需要通过一些其他手段，例如，我们可以把这个连分数给截断，假设它是一个有限连分数。 $$ \begin{align*} 1&=1\\ 1+\frac{1}{2}&=\frac{3}{2}\\ 1+\frac{1}{2+\frac{1}{2}}&=\frac{7}{5}\\ 1+\frac{1}{2+\frac{1}{2+\frac{1}{2}}}&=\frac{17}{12} \end{align*} $$ 只要截断的这些值能收敛到 $\sqrt{2}$，那 $\sqrt{2}$ 就是这个连分数的值了。 $$ \begin{align*} 1-\sqrt{2}&\approx-0.41421356\\ \frac{3}{2}-\sqrt{2}&\approx0.08578643\\ \frac{7}{5}-\sqrt{2}&\approx-0.01421356\\ \frac{17}{12}-\sqrt{2}&\approx0.00245310 \end{align*} $$ 可以发现，截断的值越来越接近 $\sqrt{2}$。为了更简洁，我们可以将上面的值的平方与 $2$ 进行比较。 $$ \begin{align*} 1^2&=2-\frac{1}{1}\\ (\frac{3}{2})^2&=2+\frac{1}{4}\\ (\frac{7}{5})^2&=2-\frac{1}{25}\\ (\frac{17}{12})^2&=2+\frac{1}{144} \end{align*} $$ 最后得到的结果是：分子的平方和分母的平方的两倍相差 $1$。这的原理是什么呢？ ## $\sqrt{2}$ 的逼近 按照我们的计算结果，可以将截断值分为两类。 - 一类是减出来为 $1$ 的。 $$ \begin{align*} 3^2-2\times2^2&=1\\ 17^2-2\times12^2&=1 \end{align*} $$ - 一类是减出来为 $-1$ 的。 $$ \begin{align*} 1^2-2\times1^2&=-1\\ 7^2-2\times5^2&=-1 \end{align*} $$ 我们将这些截断值的分子当做横坐标，分母当做纵坐标，我们可以将截断值在坐标轴上表示出来。 ![](https://cdn.luogu.com.cn/upload/image_hosting/5kv1vi1b.png) 其中蓝点是减出来为 $-1$ 的那一类，绿点是减出来为 $1$ 的那一类。我们可以知道所有蓝点都在双曲线 $x^2-2 y^2=-1$ 上，所有绿点都在双曲线 $x^2-2 y^2=1$ 上。换句话说，这上面的点都是这两条双曲线上的整点。 特别的，这两条双曲线都有一个相同的渐近线：$y=\sqrt{2}x$。 我们连接原点和双曲线上的点，这条直线的斜率就是双曲线上的点表示的数的倒数，越远的点斜率越接近 $\frac{\sqrt{2}}{2}$。 为什么所有截断值都一定在这两条双曲线上？我们要看看通分的时候是怎么计算的了。 例如，截取值的第 $3,4$ 项，分别是 $\frac{7}{5}$ 和 $\frac{17}{12}$ ，它们的计算过程分别是这样： $$ \begin{equation*} \begin{split} 1+\frac{1}{2+\frac{1}{2}}&=1+\frac{2}{5}\\ &=\frac{7}{5} \end{split} \end{equation*} $$ $$ \begin{equation*} \begin{split} 1+\frac{1}{2+\frac{1}{2+\frac{1}{2}}}&=1+\frac{1}{2+\frac{2}{5}}\\ &=1+\frac{5}{12}\\ &=\frac{17}{12} \end{split} \end{equation*} $$ 很明显，它们的第一步是一模一样的，都是 $\frac{2}{5}$，而到了第二步，一个 $+1$，一个 $+2$，才产生了差异。但我们仍然可以用 $\frac{7}{5}$ 的结果，因为我们可以将 $2$ 拆成 $1+1$ ，就像这样： $$ \begin{equation*} \begin{split} 1+\frac{1}{2+\frac{1}{2+\frac{1}{2}}}&=1+\frac{1}{1+1+\frac{2}{5}}\\ &=1+\frac{1}{1+\frac{7}{5}}\\ &=1+\frac{12}{7}\\ &=\frac{17}{12} \end{split} \end{equation*} $$ 也就是说，相邻的两个截断值，有这么一个递推公式： $$ \frac{x_{i+1}}{y_{i+1}}=1+\frac{1}{1+\frac{x_{i}}{y_{i}}}=\frac{x_i+2y_i}{x_i+y_i} $$ 并且，若前一项是最简分数，后一项也不需要约分，因为： $$ \gcd(x_{i+1},y_{i+1})=\gcd(x_i+2y_i,x_i+y_i)=\gcd(x_i,y_i)=1 $$ 现在我们回到平面上，这个递推式让我们确定了平面上点的一个变换。 $$ \binom{x}{y}\to\binom{x+2y}{x+y} $$ 它不只是可以用在这些点上，它作用于整个平面。在变换后，两条双曲线会交换位置，所有点会向后移动一个位置。这种规律其实在其他双曲线上也成立。 例如，我们将 $2$ 变为 $5$，我们在双曲线 $x^2-5y^2=\pm1$ 上仍然可以找到一个变换： $$ \binom{x}{y}\to\binom{2x+5y}{x+2y} $$ 甚至在一些更奇怪的双曲线上，这个规律也成立。比如双曲线 $x^2-3y^2=\pm1$，虽然 $x^2-3y^2=-1$ 上一个整点也没有，但我们可以在 $x^2-3y^2=1$ 上也找到一个变换： $$ \binom{x}{y}\to\binom{2x+3y}{x+2y} $$ 这个递推关系是普适的，它能让我们从一个整点推导出下一个整点，也是 Pell 方程解的递推核心。 ## Pell 方程 我们将我们上述的双曲线一般化，就得到了Pell方程的一般形式。 标准 Pell 方程： $$ x^2-ny^2=1 $$ 负 Pell 方程： $$ x^2-ny^2=-1 $$ 其中 $n$ 为正整数。 ## 解的存在条件 ### 标准 Pell 方程的解的存在性 若 $n$ 是完全平方数，设 $n=s^2 (s\in\mathbb{N})$，则方程可变形为 $$ (x-sy)(x+sy)=1 $$ 因为 $x,y$ 都是正整数，所以 $$ x-sy=x+sy=1 $$ 因此方程只有平凡解 $(\pm1,0)$，不存在正整数解。 若 $n$ 不是完全平方数，则方程一定有无穷多组正整数解。 ### 负 Pell 方程的解的存在性 1. 必要条件 $1$： 若 $n$ 是完全平方数，设 $n=s^2 (s\in\mathbb{N})$，则方程可变形为 $$ (x-sy)(x+sy)=-1 $$ 不存在正整数解。 2. 必要条件 $2$： 另外，对于 $n$ 的每个素因子 $p$，如果 $p\equiv3\pmod{4}$，必须满足 $p$ 在 $n$ 的分解中出现偶数次，负 Pell 方程才可能有解。 因为负 Pell 方程本质上求： $$ x^2\equiv-1\pmod{n} $$ 由 Legendre 符号可知： $$ \binom{-1}{p}=(-1)^{\frac{p-1}{2}} $$ 若 $p\equiv1$ 或 $2\pmod{4} \to$ 有解。 若 $p\equiv3\pmod{4}$ 且指数不为偶数 $\to$ 无解。 3. 充要条件： $\sqrt{n}$ 的连分数周期为奇数。 这是因为标准 Pell 方程的基本解来自连分数周期的末尾，而负 Pell 方程的基本解来自连分数周期的“半周期”位置。 只有当周期长度为奇数时，“半周期”才会落在整数步上，负 Pell 方程才会有解。 ## 基本解的求法 我们定义对于有解的 Pell 方程，满足所有正整数解中 $x$ 最小的那一组解 $(x_0,y_0)$，称为该方程的最小正整数解（也叫基本解）。 无论是标准 Pell 方程还是负 Pell 方程，求基本解的唯一核心方法，就是对无理数 $\sqrt{n}$ 做无限循环连分数展开，这也是求 Pell 方程基本解的通用、唯一的有效方法。 已知 $n$ 为非完全平方数，$\sqrt{n}$ 的无限循环连分数展开式的标准形式为： $$ \sqrt{n}=[a_0;\overline{a_1,a_2,\dots,a_{l-1}}] $$ 其中： - $a_0=\lfloor\sqrt{n}\rfloor$。 - $\overline{a_1,a_2,\dots,a_{l-1}}$ 是连分数的循环节，循环节长度为 $l$。 - 连分数是对称循环的，即 $a_1=a_{l-1},a_2=a_{l-2}\dots$。 我们通过四个核心变量的递推，完成连分数展开，同时得到展开后的渐近分数 $\frac{p_k}{q_k}$。 ### 初始化 $m_0=0,d_0=1,a_0=\lfloor\sqrt{n}\rfloor

渐近分数初始项：p_{-1}=1,p_0=a_0,q_{-1}=0,q_0=1

递推公式：

\begin{cases} m_{k+1}=d_k\cdot a_k-m_k\\ d_{k+1}=\frac{n-m_{k+1}^2}{d_k}\\ a_{k+1}=\lfloor\frac{a_0+m_{k+1}}{d_{k+1}}\rfloor \end{cases}

同时，渐近分数同时递推：

\begin{cases} p_{k+1}=a_{k+1}\cdot p_k+p_{k-1}\\ q_{k+1}=a_{k+1}\cdot q_k+q_{k-1} \end{cases}

当递推到 d_{k+1}=1 时，停止递推，此时我们得到了 \sqrt{n} 的连分数展开的完整循环节，循环节长度为 l。

求解

对于非完全平方数 n 的标准Pell方程，其基本解的取值由循环节长度 l 决定：

对于有解的负 Pell 方程，循环节长度 l 为奇数，其基本解为 (x_0,y_0)=(p_{l-1},q_{l-1})

现在我们就能得到方程的基本解了。

基本解与全部解的关系

所有有解的 Pell 方程，已知基本解，就能推出全部正整数解，这也是 Pell 方程的核心价值所在，所有解的递推都基于基本解。

标准 Pell 方程的全部解

设标准 Pell 方程的基本解为 (x_1,y_1)，则其所有正整数解满足递推公式：

\begin{cases} x_{k+1}=x_1\cdot x_k+n\cdot y_1\cdot y_k\\ y_{k+1}=x_1\cdot y_k+y_1\cdot x_k \end{cases}

等价于：

x_k+y_k \sqrt{n}=(x_1+y_1\sqrt{n})^k

设负 Pell 方程的基本解为 (x_0,y_0)，则其所有正整数解满足：

x_k+y_k \sqrt{n}=(x_0+y_0\sqrt{n})^{2k-1}

同时，我们可以发现，负 Pell 方程的基本解平方后，就是对应标准 Pell 方程的基本解：

x_1+y_1\sqrt{n}=(x_0+y_0\sqrt{n})^2

代码

:::success[C++]

#include<bits/stdc++.h>
#define int long long
#define i128 __int128
#define y1 Y1
using namespace std;
void write(i128 x){ //输出一个__int128的数
    if(x<0) cout<<'-',x=-x;
    if(x>9) write(x/10);
    cout<<(int)(x%10);
}
bool is2(int n){ //判断是否为平方数
    int s=sqrtl(n);
    return s*s==n;
}
void pell(int n){ //求解 Pell 方程
    i128 x1=-1,y1=-1,x2=-1,y2=-1;
    if(is2(n)){ //平方数，无解
        cout<<"-1 -1\n-1 -1\n";
        return;
    }
    //--------初始化--------
    int a0=sqrtl(n),m=0,d=1,a=a0;
    i128 ppre=1,p=a0,qpre=0,q=1,pp,qq;
    int l=0; //循环节
    //--------递推--------
    while(1){
        m=d*a-m;
        d=(n-m*m)/d;
        a=(a0+m)/d;
        l++;
        pp=(i128)a*p+ppre;
        qq=(i128)a*q+qpre;
        ppre=p,p=pp,qpre=q,q=qq;
        if(d==1) break; //循环节结束
    }
    if(l%2==0){ //循环节长度为偶数
        x1=ppre;
        y1=qpre;
    }
    else{ //循环节长度为奇数
        x2=ppre;
        y2=qpre;
        //标准基本解是负基本解平方
        x1=x2*x2+(i128)n*y2*y2;
        y1=2*x2*y2;
    }
    write(x1);
    cout<<' ';
    write(y1);
    cout<<'\n';
    write(x2);
    cout<<' ';
    write(y2);
    cout<<'\n';
}
int t,n;
signed main(){
    cin>>t;
    while(t--){
        cin>>n;
        pell(n);
    }
    return 0;
}

提交记录 :::

后记

总体来说，只要搞懂了其中的原理，这道题还是蛮简单的。

如果这篇题解有什么不对的地方，欢迎指出，谢谢观看。