Description：

对于给定正整数 $N$ ，其中 $N$ 不是完全平方数，求方程 $x^2−Ny^2=1$ 的最小正整数根。

Solution：

前置知识1：连分数

一个实数 $\omega$ 可以用一个正整数序列 $[a_0,a_1,a_2,\cdots]$ 表示，其中： $$ \omega=\mathop{\LARGE\mathrm K}_{i=1}^\infty \frac1{a_i}=a_0+\cfrac1{a_1+\cfrac1{a_2+\cfrac1{a_3+\cdots}}} $$ 数列 $\{a\}$ 的计算方法是： $$ \begin{align} \omega_0&=\omega\\ a_n&=\lfloor\omega_n\rfloor\\ \omega_{n+1}&=\cfrac{1}{\omega_n-a_n} \end{align} $$ 不难发现，如果 $\omega$ 是有理数，那么设 $\omega_n=\frac pq$ ： $$ \omega_{n+1}=\frac1{\omega_n-a_n}=\frac1{\frac pq-a_n}=\frac q{p-\lfloor\frac pq\rfloor q} $$ 那么不难发现 $p$ 和 $q$ 的操作关系类似欧几里得辗转相除法，因此这个序列一定有限，而且长度在 $O(\log(\max(p,q)))$ 级别，那么相对的，如果 $\omega$ 是无理数，那么这个序列一定是无限的。

如果一个实数 $\omega$ 的连分数表示是 $[a_0,a_1,a_2,\cdots]$ ，那么 $[a_0,a_1,a_2,\cdots,a_n]$ 称作 $\omega$ 的 $n$ 渐近分数 ，并且这个分数 $\frac pq$ 一定是 最优渐近分数 ，即对于所有分母 $\leqslant q$ 的分数中 $|\omega-\frac pq|$ 最小。

考虑如果给出 $\{a\}$ 如何计算 $\omega$ ，那么我们实际上就是要计算这个东西： $$ v_i=\frac{p_i}{q_i}=a_i+\frac1{v_{i-1}}=a_i+\frac1{\frac {p_{i-1}}{q_{i-1}}}=a_i+\frac{q_{i-1}}{p_{i-1}}=\frac{a_i{p_{i-1}}+q_{i-1}}{p_{i-1}} $$ 不难证明如果 $p\bot q$ 那么 $a_ip+q\bot q$ ，也就是说我们不用约分。

但是这个方法有一个局限性，就是我们不能直接用这个方法用有理数逼近无理数，因为每次都要重新计算一遍，复杂度是 $O(n^2)$ 的。

但是实际上是有办法解决的，我们把转移写成矩阵的形式： $$ \begin{bmatrix}p_i\\q_i\end{bmatrix}=\begin{bmatrix}a_i&1\\1&0\end{bmatrix}\times\begin{bmatrix}p_{i-1}\\q_{i-1}\end{bmatrix} $$ 也就是说： $$ \begin{bmatrix}p_n\\q_n\end{bmatrix}=\prod_{i=0}^nA_i\times\begin{bmatrix}1\\0\end{bmatrix} $$ 由于矩阵乘法具有结合律，因此我们只要从左往右计算这个式子的值就行了，那么我们只要随时维护这个矩阵，就不用每次重新计算一遍，也就是说可以直接按照上面那个式子用有理数逼近无理数，用 $O(n)$ 的时间得到 $\omega$ 的 $n$ 渐近分数。

如果把矩阵乘法展开的话可以得到这样一个更加优美的形式： $$ \begin{align} p_i&=a_ip_{i-1}+p_{i-2}\\ q_i&=a_iq_{i-1}+q_{i-2} \end{align} $$ 这样我们就可以在完全不损失精度的情况下计算 $\omega$ 的值，这个式子也从一个侧面说明了对于有理数 $\{a\}$ 的长度是 $\log \omega$ 级别的。

前置知识2： $\texttt{Pell}$ 方程

$$ x^2-Ny^2=1 $$

其实就是题目要求求解的方程。

以下直接给出结论：

$1$ 、令 $\frac{p_n}{q_n}$ 为 $\sqrt N$ 的 $n$ 渐进分数，存在 $n>0$ ，使得： $$ p_n^2-Nq_n^2=1 $$ 并且所有满足条件的 $n$ 中最小的那个对应了这个 $Pell$ 方程的最小解。

这样我们就得到了一个直接的做法，就是在不断逼近 $\sqrt N$ 的过程中顺便判断一下，但是这样每次都需要计算 $\omega _n$ ，对于比较大的 $\omega$ 会产生精度误差。

$2$ 、存在整数 $g_n$ 和 $h_n$ 满足： $$ \omega_n=\frac{g_n+\sqrt N}{h_n} $$ 把 $\omega_n=\frac1{\omega_{n-1}-a_n}$ 代入： $$ \begin{align} \omega_n&=\frac1{\omega_{n-1}-a_n}\\ &=\frac1{\frac{g_{n-1}+\sqrt N}{h_{n-1}}-a_n}\\ &=\frac{h_{n-1}}{\sqrt N+g_{n-1}-a_nh_{n-1}}\\ &=\frac{h_{n-1}(\sqrt N-g_{n-1}+a_nh_{n-1})}{(\sqrt N+g_{n-1}-a_nh_{n-1})(\sqrt N-g_{n-1}+a_nh_{n-1})}\\ &=\frac{h_{n-1}(\sqrt N-g_{n-1}+a_nh_{n-1})}{N-(g_{n-1}-a_nh_{n-1})^2}\\ &=\frac{\sqrt N-g_{n-1}+a_nh_{n-1}}{\frac{N-(g_{n-1}-a_nh_{n-1})^2}{h_{n-1}}}\\ \end{align} $$ 于是得到： $$ \begin{align} g_i&=a_ih_{i-1}-g_{i-1}\\ h_i&=\frac{N-g_i^2}{h_{i-1}}\\ a_i&=\lfloor\omega_{n-1}\rfloor=\Big\lfloor\frac{g_{i-1}+\sqrt N}{h_{i-1}}\Big\rfloor=\Big\lfloor\frac{g_{i-1}+\lfloor\sqrt N\rfloor}{h_{i-1}}\Big\rfloor \end{align} $$ 于是我们就得到了一个 完全不包含浮点误差 的做法，完美的解决了这道题。

再回到本题：