🧠 题解思路

本题考察的是著名的不定方程Pell 方程的最小正整数解。

✅ Pell 方程定义

Pell 方程的标准形式为：

𝑥 2 − 𝑁 𝑦 2

1 x 2 −Ny 2 =1 对于非完全平方数 $N$，该方程通常有无穷多个正整数解，最小正整数解 $(x_1, y_1)$ 被称为基本解，后续所有解可通过递推得到。

✅ 判断无解的条件

若 $N$ 是一个完全平方数，即存在整数 $a$ 使得 $a^2 = N$，则方程无正整数解；

否则方程总有解（来源：数论理论 + 连分数法证明）；

✅ 求解方法（连分数展开）

利用 $\sqrt{N}$ 的连分数周期展开，可以构造出 Pell 方程的解。其基本步骤如下：

判断 $N$ 是否为平方数；

对 $\sqrt{N}$ 进行连分数展开，找到周期；

根据周期奇偶性，计算出基本解 $(x_1, y_1)$；

输出基本解。

✅ 注意事项

最小解的 $x, y$ 可能非常大，需要用高精度整数（如 Python 的 int 类型 或 Java 的 BigInteger）；

C++ 可以使用 GMP 库 或实现自定义大数类；

时间复杂度受周期展开影响，一般 $\mathcal{O}(\log N)$ 到 $\mathcal{O}(\sqrt{N})$。

代码实现