题解：P14551 【模板】Pell 方程

nekob0y · 2026-07-22 18:17:28 · 题解

本题解不使用连分数法，此题解使用 Chakravala 法。

:::info[AI 使用说明] 本文在写作完成后使用 DeepSeek-R1 进行了润色。 :::

:::info[工具使用说明] 本文在写作完成后使用格式化工具进行了润色，仅对部分行修改。 :::

题意很清楚，不再赘述。

这是对于我写的 EQU2 - Yet Another Equation 题解的引用和补充。

解法

连分数法太难了，此题解使用 Chakravala 法。

考虑给式子变形：(\frac{x}{y})^2 = n + \frac{1}{y^2}，此时理论上 \frac{x}{y} 和 \sqrt{n} 较为接近，可以方便得到近似值。

什么连分数的太难了不会，那么 ——Chakravala 法。

变换

题目问：x^2 - ny^2 = 1，如果不是 1 或 -1 怎么做，例如我们已经得到一个近似值。

就是我们现在有一个 x^2 - ny^2 = k 考虑变换。

对于一个任意值 t，此时 Chakravala 法已经帮助我们构造好了一种变换形式（数学直觉惊人）：

带进去，显然可证（初中知识）。

选值

只要有几个好的 t 值，我们就可以使得 k = 1。

我们需要正整数解，所以此时的 x'、y' 和 k' 都得是整数，所以 x + yt 一定要整除 k。

为什么不用考虑 x'，因为原方程保证了 x^2 \equiv n y^2 \pmod{|k|}，而现在又保证了 x \equiv -yt \pmod{|k|}，也就是 x^2 \equiv y^2 t^2 \pmod{|k|}，所以当然 t^2 \equiv n \pmod{|k|}，最终保证了 xt + ny \equiv 0 \pmod{|k|}。

所以条件其一也就是解 y \cdot t \equiv -x \pmod{|k|}。

如果 \gcd(y, |k|) = 1，那么 t 模 |k| 的值固定，而我们一定要使得 \gcd(y, |k|) = 1，如果 \gcd(y, |k|) = d，那么 d \mid x 是显然的，那么为了最小解……

我们要 t^2 - n 尽量靠近 k。贪心的，所以接下来就是解同余方程，选择最好的 t。

特殊剪枝

对于 k = -1 的情况，就是负 Pell 方程，当前它的 x^2 - n y^2 = k = -1。

初中数学告诉我们 (x-y)^2 + 4xy = (x+y)^2，平方然后适当的分解，然后得到 (x^4 + n^2y^4 + 2nx^2y^2) - n(2xy)^2 = 1。

如果 (x, y) 是 x^2 - n y^2 = -1 的解，那么：

一定是 X^2 - n Y^2 = 1 的解。

无解

首先，标准的 Pell 方程 I 类其实只需要判断 n 是否是完全平方数即可。

那么，负 Pell 方程呢？

根据特殊剪枝，标准的有解负 Pell 方程也有解。

由于 Chakravala 运算中，先出现 k = -1 再出现 k = 1（不证明因为证明要连分数，或者 k = -1 意味着连分数周期为奇数），那么由于 k = 1 一定出现（否则特判过了）。若此时 k = -1 没遍历过，那么 k = -1 就一定无解。

补充：这个性质的证明需要用到连分数理论的一个经典结论：负 Pell 方程有解，当且仅当 \sqrt{n} 的连分数周期长度为奇数。Chakravala 法与连分数法本质是等价的，因此这个判定准则也适用于 Chakravala 法。

复杂度

似乎玄学，但是 Accepted，而且跑得飞快。

当然你知道定理后打表当然也可以了（打得很快）。

代码

#include <bits/stdc++.h>
#define int __int128

using namespace std;

using i64 = long long;

ostream & operator << (ostream & os, int val) {
    if (not val) return os << 0;

    stack<char> ret;

    if (val < 0) os << '-', val = -val;

    for (; val; val /= 10) ret.push((val % 10) + '0');
    for (; not ret.empty(); ret.pop()) os << ret.top();

    return os;
}

i64 T, n;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    for (cin >> T; T; T --) {
        cin >> n;

        int a = sqrtl(n);
        while ((a + 1) * (a + 1) <= n) a ++;
        while (a * a > n) a --;

        if (a * a == n) {
            cout << "-1 -1" << '\n';
            cout << "-1 -1" << '\n';
            continue;
        }

        int b = 1, k = a * a - n;

        int X1 = -1, Y1 = -1;
        int X2 = -1, Y2 = -1;
        bool f1 = false, f2 = false;

        for (int i = 1; i <= 80; i ++) {
            if (k == -1) {
                if (!f2) X2 = a, Y2 = b, f2 = true;

                if (!f1) {
                    X1 = a * a + n * b * b;
                    Y1 = 2 * a * b; f1 = true;
                }

                break;
            }

            if (k == 1) {
                if (!f1) X1 = a, Y1 = b, f1 = true;
                if (!f2) X2 = -1, Y2 = -1, f2 = true;

                break;
            }

            int abs_k = k > 0 ? k : -k;
            int ret = 1,  mn = -1;

            for (int t = 1; t <= 4000; t ++)
                if ((a + b * t) % abs_k == 0) {
                    int d = t * t - n; 
                    if (d < 0) d = -d;
                    if (mn == -1 || d < mn)
                        mn = d, ret = t;
                    if (t * t > n) break;
                }

            int A = (a * ret + n * b) / abs_k;
            int B = (a + b * ret) / abs_k;
            int K = (ret * ret - n) / k;
            a = A, b = B, k = K;
        }

        if (X1 == -1) cout << "-1 -1\n";
        else cout << X1 << ' ' << Y1 << '\n';

        if (X2 == -1) cout << "-1 -1\n";
        else cout << X2 << ' ' << Y2 << '\n';
    }

    return 0;
}