Continued Fraction

$$
x = a_0+\dfrac{1}{a_1+\dfrac{1}{a_2+\dfrac{1}{\cdots+\dfrac{1}{a_n}}}}.
$$

连分数有意义，当且仅当对应的展开式有意义．这些 $a_k$ 称为连分数的 **项**（term）或 **系数**（coefficient）．

$$
x = \lim_{k\rightarrow\infty} x_k = \lim_{k\rightarrow\infty} [a_0,a_1,\cdots,a_k].
$$

连分数有意义，当且仅当对应的极限有意义．其中，$x_k=[a_0,a_1,\cdots,a_k]$ 称为 $x$ 的第 $k$ 个 **渐近分数**（convergent）或 **收敛子**，而 $r_k=[a_k,a_{k+1},\cdots]$ 称为 $x$ 的第 $k$ 个 **余项** 或 **完全商**（complete quotient）．相应地，项 $a_k$ 有时也称为第 $k$ 个 **部分商**（partial quotient）．

1.  对于任意 $k\in\mathbf Z$，有 $x+k=[a_0+k,a_1,a_2,\cdots]$；
2.  对实数 $x>1$，有 $a_0>0$，且它的倒数 $x^{-1}=[0,a_0,a_1,a_2,\cdots]$．

$$
\begin{aligned}
x = [1,1,1,1] &= 1+\dfrac{1}{1+\dfrac{1}{1+\dfrac{1}{1}}},\\
x = [1,1,2] &= 1+\dfrac{1}{1+\dfrac{1}{2}}.
\end{aligned}
$$

=== "C++"
    ```cpp
    --8<-- "docs/math/code/continued-fraction/diophantine.cpp:fraction"
    ```

=== "Python"
    ```py
    --8<-- "docs/math/code/continued-fraction/diophantine.py:fraction"
    ```

$$
\begin{aligned}
x_0 &= [1]=1,\\
x_1 &= [1,1]=2,\\
x_2 &= [1,1,1]=\dfrac{3}{2},\\
x_3 &= [1,1,1,1]=\dfrac{5}{3},\\
x_4 &= [1,1,1,1,1]=\dfrac{8}{5}.
\end{aligned}
$$

可以归纳地证明

$$
x_k = \frac{F_{k+2}}{F_{k+1}},
$$

其中，$\{F_k\}$ 是 [斐波那契数列](../combinatorics/fibonacci.md)．根据它的通项公式可知，

$$
x_k = \frac{\phi^{k+2}-(-\phi)^{-(k+2)}}{\phi^{k+1}-(-\phi)^{-(k+1)}},
$$

其中的 $\phi=\dfrac{1+\sqrt{5}}{2}$ 是黄金分割比．当 $k$ 趋于无穷时，有

$$
x=\lim_{k\rightarrow\infty}x_k=\phi.
$$

因而，连分数 $x=[1,1,1,1,\cdots]$ 表示的是黄金分割比 $\phi$．

$$
\begin{aligned}
p_k &= a_kp_{k-1}+p_{k-2},\\
q_k &= a_kq_{k-1}+q_{k-2}.
\end{aligned}
$$

递推的起点是（形式）分数

$$
x_{-1}=\frac{p_{-1}}{q_{-1}}=\frac{1}{0},\ x_{-2}=\frac{p_{-2}}{q_{-2}}=\frac{0}{1}.
$$

$$
r_k = \frac{P_k(a_0, a_1, \cdots, a_k)}{Q_k(a_0,a_1, \cdots, a_k)}.
$$

根据渐近分数的定义，有

$$
r_k = a_0 + \frac{1}{[a_1,a_2,\cdots, a_k]}= a_0 + \frac{Q_{k-1}(a_1, \cdots, a_k)}{P_{k-1}(a_1, \cdots, a_k)} = \frac{a_0 P_{k-1}(a_1, \dots, a_k) + Q_{k-1}(a_1, \cdots, a_k)}{P_{k-1}(a_1, \cdots, a_k)}.
$$

和上式比较，不妨设 $Q_k(a_0, \cdots, a_k) = P_{k-1}(a_1, \cdots, a_k)$，就可以将渐近分数写作

$$
r_k =  \frac{P_k(a_0, a_1, \cdots, a_k)}{P_{k-1}(a_1, \cdots, a_k)}
$$

且多项式 $P_k$ 有递推关系

$$
P_k(a_0, \cdots, a_k) = a_0 P_{k-1}(a_1, \cdots, a_k) + P_{k-2}(a_2, \cdots, a_k).
$$

因为

$$
r_0 = a_0,\ r_1 = a_0+\dfrac{1}{a_1} = \frac{a_0a_1+1}{a_1},
$$

所以，递推的起点是

$$
P_0(a_0) = a_0,\ P_1(a_0,a_1) = a_0a_1 + 1.
$$

如果设

$$
P_{-1} = 1,\ P_{-2} = 0,
$$

可以验证对于 $k=0,1$ 也成立上述递推关系．这相当于规定了形式分数 $r_{-1}=\dfrac{1}{0}$ 和 $r_{-2}=\dfrac{0}{1}$．

满足上述递推关系的多项式列 $P_k$ 称为 **连项式**[^continuant]（continuant）．它可以写作行列式的形式：

$$
P_k(a_0,\cdots,a_k)=\det
\begin{pmatrix}
a_0 & 1 & 0 & \cdots & 0 \\
-1 & a_1 & 1 & \ddots & \vdots \\
0 & -1 & a_2 & \ddots & 0 \\
\vdots & \ddots & \ddots & \ddots & 1 \\
0 & \cdots & 0 & -1 & a_k
\end{pmatrix}.
$$

这是一个 [三对角矩阵](https://en.wikipedia.org/wiki/Tridiagonal_matrix) 的行列式，从左上角开始展开，可以验证它具有上面的递推关系和初值条件．反过来，从右下角开始展开，则又能得到递推关系

$$
P_k(a_0, \cdots, a_k) = a_k P_{k-1}(a_0, \cdots, a_{k-1}) + P_{k-2}(a_0, \cdots, a_{k-2}),
$$

这就是所要求证的．

$$
\begin{aligned}
\frac{p_k}{p_{k-1}}&=[a_k,a_{k-1},\cdots,a_1,a_0],\\
\frac{q_k}{q_{k-1}}&=[a_k,a_{k-1},\cdots,a_1].
\end{aligned}
$$

如果 $a_0=0$，则第一个连分数应当理解为在倒数第二项处截断，即 $[a_k,a_{k-1},\cdots,a_2]$．

$$
\begin{aligned}
\frac{p_k}{p_{k-1}} &= a_k + \frac{p_{k-2}}{p_{k-1}},\\
\frac{q_k}{q_{k-1}} &= a_k + \frac{q_{k-2}}{q_{k-1}}.
\end{aligned}
$$

迭代这两个式子，就可以得到两个连分数．再代入初始值 $\dfrac{p_0}{p_{-1}}=a_0$ 和 $\dfrac{q_1}{q_0}=a_1$ 即可．至于 $a_0=0$ 的情形，将得到的连分数理解为形式表达式，则它的余项

$$
[a_2,a_1,0]=a_2+\dfrac{1}{a_1+\dfrac{1}{0}}=a_2+\dfrac{0}{0a_1+1}=a_2.
$$

因而可以直接略去最后两项．如果需要严格的证明，只要注意到这个式子可以看作 $a_0\rightarrow 0$ 的极限即可．

=== "C++"
    ```cpp
    --8<-- "docs/math/code/continued-fraction/diophantine.cpp:convergents"
    ```

=== "Python"
    ```py
    --8<-- "docs/math/code/continued-fraction/diophantine.py:convergents"
    ```

$$
p_{k+1}q_k − p_kq_{k+1} = (−1)^k.
$$

因此，相邻两项的渐近分数的差分是

$$
x_{k+1} - x_k = \dfrac{(-1)^k}{q_{k+1}q_k}.
$$

$$
\begin{aligned}
\det\begin{pmatrix}
p_{k+1} & p_k \\
q_{k+1} & q_k 
\end{pmatrix}
&=
\det\begin{pmatrix}
a_{k+1}p_{k}+p_{k-1} & p_k \\
a_{k+1}q_{k}+q_{k-1} & q_k 
\end{pmatrix}
=
\det\begin{pmatrix}
p_{k-1} & p_k\\
q_{k-1} & q_k
\end{pmatrix}
\\
&=
-
\det\begin{pmatrix}
p_k & p_{k-1}\\
q_k & q_{k-1}
\end{pmatrix}
=
(-1)^{k+2}
\det\begin{pmatrix}
1 & 0\\
0 & 1
\end{pmatrix}
=(-1)^k.
\end{aligned}
$$

这就是 $p_{k+1}q_k − p_kq_{k+1} = (−1)^k$．对两边同除以 $q_{k+1}q_k$，就得到关于 $x_{k+1}-x_k$ 的结论．

$$
x_k - x = \dfrac{(-1)^k}{q_k\left(r_{k+1}q_k+q_{k-1}\right)},
$$

其中，$r_{k+1}$ 是实数 $x$ 的第 $k+1$ 个余项．进而，有

$$
\dfrac{1}{2q_{k+1}^2} \le \dfrac{1}{q_k(q_k+q_{k+1})} \le \left|x-\frac{p_k}{q_k}\right| \le \dfrac{1}{q_kq_{k+1}} \le \dfrac{1}{q_k^2}.
$$

$$
x-x_k = \dfrac{(-1)^k}{q_k\left(r_{k+1}q_k+q_{k-1}\right)},
$$

其中，$r_{k+1}q_k+q_{k-1}$ 就是按照递推公式得到的这个形式连分数的第 $k+1$ 个渐近分数的分母．

要完成随后的不等式估计，只需要注意到当 $x_k\neq x$ 时，总成立

$$
1\le a_{k+1}\le r_{k+1} \le a_{k+1}+1,
$$

所以有

$$
q_{k+1}=a_{k+1}q_k+q_{k-1}\le r_{k+1}q_k+q_{k-1} \le q_k+(a_{k+1}q_k+q_{k-1}) = q_k+q_{k+1}.
$$

因此，有不等式

$$
\dfrac{1}{q_k(q_k+q_{k+1})} \le \left|x-\frac{p_k}{q_k}\right| = \dfrac{1}{q_k\left(r_{k+1}q_k+q_{k-1}\right)} \le \dfrac{1}{q_kq_{k+1}}.
$$

要得到外侧的放缩，再注意到 $q_k\le q_{k+1}$ 就可以了．

设 $\dfrac{A}{B}=[a_0, a_1, \cdots, a_k]$．上面证明了 $p_k q_{k-1} - p_{k-1} q_k = (-1)^{k-1}$．将 $p_k$ 和 $q_k$ 替换为 $A$ 和 $B$，得到

$$
Aq_{k-1} - Bp_{k-1} = (-1)^{k-1} g,
$$

其中，$g = \gcd(A, B)$．如果 $g$ 整除 $C$，则一组解为 $x = (-1)^{k-1}\dfrac{C}{g} q_{k-1}$ 和 $y = (-1)^{k}\dfrac{C}{g} p_{k-1}$；否则无解．

=== "C++"
    ```cpp
    --8<-- "docs/math/code/continued-fraction/diophantine.cpp:dio"
    ```

=== "Python"
    ```py
    --8<-- "docs/math/code/continued-fraction/diophantine.py:dio"
    ```

$$
\left|x-\dfrac{p}{q}\right| < \dfrac{1}{q^2} 
$$

成立．

$$
\left|x-\dfrac{p_k}{q_k}\right|\le\frac{1}{q_k^2}.
$$

检查误差公式的证明即可知，对于任一无理数 $x$，取等条件并不成立．因此，它的所有渐近分数的分子和分母都满足要求．

$$
\left|x-\dfrac{p}{q}\right| < \dfrac{1}{\sqrt{5}q^2} 
$$

成立，而且不等式右侧的 $\sqrt{5}$ 不能换成更大的实数．

反证法．不妨设存在无理数 $x$ 和它的渐近分数 $x_{k-1},x_k,x_{k+1}$，使得

$$
\left|x-\dfrac{p_{k-1}}{q_{k-1}}\right|\ge\dfrac{1}{\sqrt{5}q_{k-1}^2},\ 
\left|x-\dfrac{p_{k}}{q_{k}}\right|\ge\dfrac{1}{\sqrt{5}q_{k}^2},\ 
\left|x-\dfrac{p_{k+1}}{q_{k+1}}\right|\ge\dfrac{1}{\sqrt{5}q_{k+1}^2}
$$

成立．因为相邻的渐近分数必然位于 $x$ 两侧，所以由差分公式知

$$
\dfrac{1}{q_{k-1}q_{k}}=\left|\dfrac{p_{k-1}}{q_{k-1}}-\dfrac{p_{k}}{q_{k}}\right|=\left|x-\dfrac{p_{k-1}}{q_{k-1}}\right|+\left|x-\dfrac{p_{k}}{q_{k}}\right|\ge\dfrac{1}{\sqrt{5}q_{k-1}^2}+\dfrac{1}{\sqrt{5}q_{k}^2}.
$$

它可以写成关于商 $\dfrac{q_{k}}{q_{k-1}}$ 的不等式

$$
\dfrac{q_k}{q_{k-1}}+\dfrac{q_{k-1}}{q_k}\le\sqrt 5.
$$

因为左侧是有理数，右侧是无理数，等号必然无法取得．又因为 $q_k\ge q_{k-1}$，所以可以解得

$$
1\le \dfrac{q_{k}}{q_{k-1}} < \dfrac{\sqrt{5}+1}{2}.
$$

同理，可以证明

$$
1\le \dfrac{q_{k+1}}{q_{k}} < \dfrac{\sqrt{5}+1}{2}.
$$

但是根据递推公式，并结合两式可知，

$$
a_{k+1} = \frac{q_{k+1}}{q_k}-\frac{q_{k-1}}{q_k} < \dfrac{\sqrt{5}+1}{2}-\dfrac{\sqrt{5}-1}{2} = 1
$$

这与简单连分数的定义矛盾．所以，Borel 的结论成立．

要说明这样得到的界是最好的，只需要找到 $x$ 使得对于任何 $C>\sqrt{5}$，都只存在有限多个既约分数 $\dfrac{p}{q}$ 使得不等式

$$
\left|x-\dfrac{p}{q}\right| < \dfrac{1}{Cq^2} 
$$

成立．下面证明 $\phi=\dfrac{\sqrt{5}+1}{2}$ 就是这样的 $x$．[^sqrt5]

设 $\phi'=\dfrac{-\sqrt{5}+1}{2}$ 是 $\phi$ 的共轭根．它们都是方程 $x^2-x-1=0$ 的根．因而，对任意实数 $x$，都有

$$
x^2-x-1 = (x-\phi)(x-\phi').
$$

代入既约分数 $\dfrac{p}{q}$，就得到

$$
\dfrac{1}{q^2}\le\frac{|p^2-pq-q^2|}{q^2}=\left|\dfrac{p}{q}-\phi\right|\left|\dfrac{p}{q}-\phi'\right|\le\left|\dfrac{p}{q}-\phi\right|\left(\left|\dfrac{p}{q}-\phi\right|+|\phi-\phi'|\right)<\dfrac{1}{Cq^2}\left(\dfrac{1}{Cq^2}+\sqrt{5}\right).
$$

对于 $C>\sqrt{5}$，可以直接解出 $q<\sqrt{C(C-\sqrt{5})}$，因而不可能存在无穷多组解满足上述不等式．

$$
\left|x-\dfrac{p}{q}\right|<\left|x-\dfrac{p'}{q'}\right|,
$$

就称有理数 $\dfrac{p}{q}$ 是实数 $x$ 的 **第一类最佳逼近**（best approximation of the first kind）．

类似于渐近分数的情形，大于（小于）$x$ 的中间分数称为 **上（下）中间分数**（upper (lower) semiconvergent）．

$$
x_{1,0}<x_{1,1}< \cdots < x_{1,a_2}=x_{3,0}<\ldots<x<\ldots<x_{2,0}=x_{0,a_1}<\cdots<x_{0,1}.
$$

同阶的中间分数是连续出现的，而不同阶的中间分数之间又没有间隔．这意味着，任何位于 $x_{1,0}=a_0$ 与 $x_{0,1}=a_0+1$ 之间的有理数 $\dfrac{p}{q}$ 必然落在两个同阶的中间分数 $x_{k,t}$ 和 $x_{k,t+1}$ 之间．不妨设它不是中间分数且小于 $x$，因而有

$$
x_{k,t}<\dfrac{p}{q}<x_{k,t+1}<x.
$$

此时，一方面有

$$
\left|x_{k,t}-\dfrac{p}{q}\right| \le \left|x_{k,t}-x_{k,t+1}\right| = \dfrac{1}{((t+1)q_k+q_{k-1})(tq_k+q_{k-1})}.
$$

另一方面有

$$
\left|x_{k,t}-\dfrac{p}{q}\right| = \dfrac{|q(tp_k+p_{k-1})-p((t+1)q_k+q_{k-1})|}{q(tq_k+q_{k-1})}\ge\dfrac{1}{q(tq_k+q_{k-1})}.
$$

因此，必然有

$$
q>(t+1)q_k+q_{k-1}.
$$

也就是说，有理数 $\dfrac{p}{q}$ 的分母一定大于 $x_{k,t+1}$ 的分母，但是它并不是更好的逼近：

$$
\left|x-\dfrac{p}{q}\right|>\left|x-x_{k,t+1}\right|
$$

因此，它不可能是第一类最佳逼近．这就说明，不是中间分数，就不是第一类最佳逼近；亦即所有第一类最佳逼近都是中间分数．

前文已经说过，中间分数 $x_{k,t}$ 的分母位于 $x_k$ 和 $x_{k+1}$ 之间，且随着 $t$ 的增加逐渐增大，但是 $x_{k,t}$ 却逐渐接近 $x_{k+1}$，因而更接近 $x$．以 $x_{k,t}<x$ 为例，它与相邻的中间分数的相对位置关系满足：

$$
x_{k-1} < x_{k,t} < x_{k+1} < x < x_{k}.
$$

因为 $x_k$ 的分母小于 $x_{k,t}$，所以 $x_{k,t}$ 成为第一类最佳逼近的必要条件就是，它比 $x_k$ 更接近 $x$．这也是充分条件，因为作为渐近分数，没有比 $x_k$ 分母更小但是距离更近的了，而那些比 $x_k$ 分母还要大的中间分数，必然与 $x_{k,t}$ 同阶，但是分母更小，就必然距离 $x$ 更远．对于渐近分数和中间分数的误差，经计算可知

$$
\begin{aligned}
\left|x_k-x\right| &= \dfrac{1}{q_k(r_{k+1}q_k+q_{k-1})},\\
\left|x_{k,t}-x\right| &= \left|\dfrac{tp_{k}+p_{k-1}}{tq_{k}+q_{k-1}}-\dfrac{r_{k+1}p_{k}+p_{k-1}}{r_{k+1}q_{k}+q_{k-1}}\right| \\
&=\dfrac{r_{k+1}-t}{(tq_{k}+q_{k-1})(r_{k+1}q_{k}+q_{k-1})}.
\end{aligned}
$$

其中用到了 $r_{k+1}\ge a_{k+1}>t$．因此，$x_{k,t}$ 比 $x_k$ 更接近 $x$，成为第一类最佳逼近，当且仅当

$$
\dfrac{r_{k+1}-t}{tq_{k}+q_{k-1}}<\dfrac{1}{q_k} \iff r_{k+1}<2t+\dfrac{q_{k-1}}{q_k}.
$$

此时，有三种可能的情况：

1.  如果 $t<\dfrac{a_{t+1}}{2}$，那么 $2t<a_{t+1}$．因为两侧都是整数，所以 $2t\le a_{k+1}-1$，故而 $2t+\dfrac{q_{k-1}}{q_k}\le 2t+1\le a_{k+1}\le r_{t+1}$．此时，$x_{k,t}$ 不是第一类最佳逼近；
2.  如果 $t>\dfrac{a_{t+1}}{2}$，那么 $2t>a_{t+1}$．因为两侧都是整数，所以 $2t\ge a_{t+1}+1>r_{t+1}$．此时，$x_{k,t}$ 是第一类最佳逼近；
3.  如果 $a_{t+1}$ 是偶数，还有第三种情况，即 $t=\dfrac{a_{t+1}}{2}$．上述条件等价于 $\dfrac{1}{r_{k+1}}=r_{k+1}-a_{k+1}<\dfrac{q_{k-1}}{q_k}$，亦即 $r_{k+2}>\dfrac{q_k}{q_{k-1}}$．

$$
\begin{aligned}
&x_0 = \dfrac{3}{1},\
x_{0,4} = \dfrac{13}{4},\
x_{0,5} = \dfrac{16}{5},\
x_{0,6} = \dfrac{19}{6},\
x_1 = \dfrac{22}{7},\\
&x_{1,8} = \dfrac{179}{57},\
x_{1,9} = \dfrac{201}{64},\
x_{1,10} = \dfrac{223}{71},\
x_{1,11} = \dfrac{245}{78},\
x_{1,12} = \dfrac{267}{85},\\
&x_{1,13} = \dfrac{289}{92},
x_{1,14} = \dfrac{311}{99},\
x_2 = \dfrac{333}{106},\
x_3 = \dfrac{355}{113},\
x_{3,146} = \dfrac{52163}{16604}.
\end{aligned}
$$

$$
\left|qx-p\right|<\left|q'x-p'\right|,
$$

就称有理数 $\dfrac{p}{q}$ 是实数 $x$ 的 **第二类最佳逼近**（best approximation of the second kind）．

$$
x_{k-1} < x_{k,t} < x_{k+1} < x < x_{k}.
$$

因为 $x_{k,t}$ 与 $x$ 之间的误差

$$
|x_{k,t}-x|\ge |x_{k,t}-x_{k+1}|=\left|\dfrac{p}{q}-\dfrac{p_{k+1}}{q_{k+1}}\right|=\dfrac{|pq_{k+1}-p_{k+1}q|}{qq_{k+1}}\ge\dfrac{1}{qq_{k+1}},
$$

并利用渐近分数的误差估计，所以总是有

$$
|qx_{k,t}-p| \ge \dfrac{1}{q_{k+1}} \ge |q_kx_k-p_k|,
$$

即 $x_{k,t}$ 的逼近程度不优于分母更小的 $x_k$ 逼近程度，所以不可能是第二类最佳逼近．

反过来，要证明第二部分，即每个渐近分数 $x_k=\dfrac{p_k}{q_k}$ 都是第二类最佳逼近．这就是要说明，对于所有分数 $\dfrac{p}{q}$ 且 $q\le q_k$，都有 $|q_kx-p_k|<|qx-p|$．不考虑半奇数的情形，则可以假定 $k>0$．首先，根据渐近分数逼近实数的误差估计，有

$$
|q_{k-1} x-p_{k-1}| \ge \frac{1}{q_{k-1}+q_{k}} \ge \dfrac{1}{q_{k+1}}\ge |q_kx-p_k|.
$$

不等式全部成立等号，当且仅当 $a_{k+1}=1$ 且是连分数的末项．不考虑这样的情形，那么 $x_{k-1}=\dfrac{p_{k-1}}{q_{k-1}}$ 严格劣于 $x_k=\dfrac{p_k}{q_k}$．

任取一分数 $\dfrac{p}{q}\neq x_k$ 且 $0<q\le q_k$，因为有差分公式 $p_{k}q_{k-1} − p_{k-1}q_{k} = (−1)^{k-1}$，所以由 Cramer 法则可知，线性方程组

$$
\begin{cases}
\lambda p_k+\mu p_{k-1} = p,\\
\lambda q_k+\mu q_{k-1} = q
\end{cases}
$$

必然存在唯一的整数解 $(\lambda,\mu)$．如果 $\lambda\mu>0$，那么 $q>|\lambda|q_k\ge q_k$，矛盾．否则，$\lambda\mu\le 0$，即 $\lambda$ 和 $\mu$ 异号，那么因为 $q_{k-1}x-p_{k-1}$ 和 $q_kx-p_k$ 也异号，就有 $\lambda(q_{k-1}x-p_{k-1})$ 和 $\mu(q_kx-p_k)$ 同号，故而

$$
|qx-p|=|\lambda||q_kx-p_k|+|\mu||q_{k-1}x-p_{k-1}|>|q_{k}x-p_{k}|.
$$

最后的不等号是严格的，因为 $x_{k-1}$ 严格劣于 $x_k$，且 $\dfrac{p}{q}\neq x_k$．这就说明，$x_k$ 是第二类最佳逼近．

$$
\left|x−\dfrac{p}{q}\right|<\dfrac{1}{2q^2}
$$

那么 $\dfrac{p}{q}$ 一定是 $x$ 的渐近分数．

$$
x−\dfrac{p}{q} = \dfrac{\epsilon\theta}{q^2}
$$

成立的常数．将有理数 $\dfrac{p}{q}$ 展开成连分数 $[a_0,a_1,\cdots,a_n]$．此处，有理数有两种连分数表示，其中的 $n$ 恰好相差一，所以可以取连分数表示使得 $(-1)^n=\epsilon$，并记这个连分数表示的渐近分数为 $\dfrac{p_k}{q_k}$．设实数 $\omega$ 满足

$$
x = \dfrac{\omega p_n+p_{n-1}}{\omega q_n+q_{n-1}}.
$$

那么，必然有

$$
\dfrac{\epsilon\theta}{q^2} = x−\dfrac{p}{q} = x-\dfrac{p_n}{q_n} = \dfrac{p_{n-1}q_n-p_nq_{n-1}}{(\omega q_n+q_{n-1})q_n} = \dfrac{(-1)^n}{(\omega q_n+q_{n-1})q_n}.
$$

故而，有

$$
\theta = \dfrac{q_n}{\omega q_n+q_{n-1}}.
$$

这说明

$$
\omega=\dfrac{1}{\theta}-\dfrac{q_{n-1}}{q_n}>1.
$$

将 $\omega$ 也展成连分数 $[b_0,b_1,\cdots]$，则

$$
x = \dfrac{\omega p_n+p_{n-1}}{\omega q_n+q_{n-1}} = [a_0,a_1,\cdots,a_n,\omega] = [a_0,a_1,\cdots,a_n,b_0,b_1,\cdots].
$$

这是合法的简单连分数，所以 $\dfrac{p}{q}$ 就是 $x$ 的渐近分数．

这个证明实际说明 $\dfrac{p}{q}$ 成为渐近分数的充分必要条件是上述证明中的 $\omega>1$，这正是 Legendre 判别法的原始形式．

$$
\left|x−\dfrac{p}{q}\right|<\dfrac{1}{2q^2}.
$$

$$
\left|x-\dfrac{p_k}{q_k}\right|\ge \dfrac{1}{2q_{k}^2},\ \left|x-\dfrac{p_{k+1}}{q_{k+1}}\right|\ge \dfrac{1}{2q_{k+1}^2}.
$$

因为 $x$ 位于 $x_{k-1}$ 和 $x_k$ 之间，所以

$$
\dfrac{1}{2q_{k}^2} + \dfrac{1}{2q_{k+1}^2} \le \left|x-\dfrac{p_k}{q_k}\right| + \left|x-\dfrac{p_{k+1}}{q_{k+1}}\right| = \left|\dfrac{p_k}{q_k}-\dfrac{p_{k+1}}{q_{k+1}}\right| = \dfrac{1}{q_kq_{k+1}}.
$$

这说明 $q_k=q_{k+1}$．故而必然有 $k=0$ 且 $a_1=1$．此时前两个渐近分数是 $x_0=a_0$ 和 $x_1=a_0+1$．故而命题的唯一反例是半奇数，按照前文的说明，本文不考虑这种情形．

    $$
    \dfrac{|p-qx|}{\sqrt{1+\xi^2}},
    $$

    对应着分数 $\nu$ 对实数 $\xi$ 的逼近程度．
-   将渐近分数 $\xi_k=\dfrac{p_k}{q_k}$ 对应的点记作 $\vec\xi_k=(p_k,q_k)$，则递推公式就可以写作

    $$
    \vec\xi_k = a_k\vec\xi_{k-1} + \vec\xi_{k-2}.
    $$

    递归的起点是 $\xi_{-2} = (1,0)$ 和 $\xi_{-1} = (0,1)$．
-   对于整数 $t$，如果 $0\le t\le a_k$，那么点

    $$
    \vec\xi_{k-1,t} = t\vec\xi_{k-1} + \vec\xi_{k-2}
    $$

    就落在连结点 $\vec\xi_{k-2}$ 和点 $\vec\xi_k$ 的线段上．它们对应着中间分数 $\xi_{k-1,t}$．
-   利用几何的方法可以构造出所有的渐近分数和中间分数．从点 $\vec\xi_{-2}=(1,0)$ 和点 $\vec\xi_{-1}=(0,1)$ 开始，两个点位于直线 $y=\xi x$ 两侧，这意味着 $\vec\xi\times\vec\xi_{-2}$ 和 $\vec\xi\times\vec\xi_{-1}$ 符号相反．将 $\vec\xi_{-1}$ 按照向量的加法添加到 $\vec\xi_{-2}$ 上，直到无法继续添加而不穿过直线 $y=\xi x$ 为止，将结果记作 $\vec\xi_0$，此时仍与 $\vec\xi_{-1}$ 不同侧．再将 $\vec\xi_0$ 添加到 $\vec\xi_{-1}$ 上，直到无法继续添加而不穿过直线 $y=\xi x$ 为止，将结果记作 $\vec\xi_1$，此时仍与 $\vec\xi_0$ 不同侧．这个过程可以一直持续到无穷，除非在有限步内某个 $\vec\xi_n$ 就恰好落在直线 $y=\xi x$ 上．后者意味着向量 $\vec\xi$ 与 $\vec\xi_n$ 共线，即 $\xi=\dfrac{p_n}{q_n}$ 为有理点．这个过程就可以得到前面示意图中的图形．Boris Delaunay 将这个过程形象地称为鼻子拉伸算法（nose-streching algorithm）[^nose-streching]．
-   如果需要快速计算每一步将 $\vec\xi_{k-1}$ 添加到 $\vec\xi_{k-2}$ 需要的次数，可以借助叉积．因为 $\vec\xi\times\vec\xi_{k-1}$ 与 $\vec\xi\times\vec\xi_{k-2}$ 符号相反，所以如果记 $\vec\xi_{k-1,t}=t\vec\xi_{k-1}+\vec\xi_{k-2}$ 为向 $\vec\xi_{k-2}$ 添加 $t$ 次 $\vec\xi_{k-1}$ 得到的结果，则 $\vec\xi\times\vec\xi_{k-1,t}=t(\vec\xi\times\vec\xi_{k-1})+(\vec\xi\times\vec\xi_{k-2})$ 不改变符号，就意味着没有穿过直线．在不变号之前，$\vec\xi\times\vec\xi_{k-1,t}$ 的绝对值会逐渐下降．记

    $$
    r_{k} = \left|\dfrac{\vec\xi\times\vec\xi_{k-2}}{\vec\xi\times\vec\xi_{k-1}}\right| = -\dfrac{\vec\xi\times\vec\xi_{k-2}}{\vec\xi\times\vec\xi_{k-1}}.
    $$

    那么，最大可以下降的次数就是

    $$
    a_{k} = \lfloor r_{k}\rfloor = \left\lfloor\left|\dfrac{q_{k-1}\xi-p_{k-1}}{q_{k-2}\xi-p_{k-2}}\right|\right\rfloor.
    $$

    这就是连分数展开的第 $k$ 项．而且，$r_k$ 就是连分数展开的余项，它满足关系式：

    $$
    r_k = -\dfrac{q_{k-1}\xi-p_{k-1}}{q_{k-2}\xi-p_{k-2}} \iff \xi = \dfrac{p_{k-1}r_k + p_{k-2}}{q_{k-1}r_k+q_{k-2}}.
    $$

    这就是连分数关系式 $\xi = [a_0,a_1,\cdots,a_{k-1},r_k]$．
-   因为每次添加向量造成的 $\vec\xi\times\vec\xi_{k-1,t}$ 的变化的步长都是 $|\vec\xi\times\vec\xi_{k-1}|$，所以最后剩余的距离 $|\vec\xi\times\vec\xi_k|$ 必然严格小于 $|\vec\xi\times\vec\xi_{k-1}|$．这说明，渐近分数的逼近程度（由 $|qx-p|$ 衡量）是随着 $k$ 的增加严格更优的．
-   利用叉积的运算法则，有

    $$
    \vec\xi_{k}\times\vec\xi_{k+1} = \vec\xi_{k}\times(a_{k+1}\vec\xi_k+\vec\xi_{k-1}) = \vec\xi_{k}\times\vec\xi_{k-1} = -\vec\xi_{k-1}\times\vec\xi_{k}.
    $$

    归纳可知

    $$
    \vec\xi_{k}\times\vec\xi_{k+1} = (-1)^{k+2}\vec\xi_{k-2}\times\vec\xi_{k-1} = (-1)^{k}.
    $$

    这就是渐近分数的差分公式 $p_{k+1}q_k-p_kq_{k+1}=(-1)^k$．
-   上下两个凸包之间的面积可以剖分成若干个（可能是无穷多个）三角形，其中每个三角形的顶点分别是 $\vec\xi_{k-2}$、$\vec\xi_k$ 和 $\vec 0$．这样的三角形的面积是

    $$
    \dfrac12|\vec\xi_{k-2}\times\vec\xi_k| = \dfrac12|\vec\xi_{k-2}\times(a_k\vec\xi_{k-1}+\vec\xi_{k-2})| = \dfrac{a_k}{2}|\vec\xi_{k-2}\times\vec\xi_{k-1}| = \dfrac{a_k}{2}.
    $$

    根据 [Pick 定理](../../geometry/pick.md)，这意味着如果设 $I$ 和 $B$ 分别为三角形内部和边界上的整点个数，则

    $$
    I + \dfrac{B}{2} - 1 = \dfrac{a_k}{2}.
    $$

    又已知三角形边界上已经有了 $\{\vec 0\}\cup\{\vec\xi_{k-1,t}:0\le t\le a_k\}$ 这共计 $a_k+2$ 个整点．这说明，就一定有 $I=0$ 和 $B=a_k+2$．因而，三角形的边上没有更多的整点，三角形内部也没有整点．也就是说，$q_k$ 和 $p_k$ 是既约的，中间分数是连结 $\vec\xi_{k-2}$ 和 $\vec\xi_k$ 的边上的全部整点，且第一象限的所有整点都在上下两个凸包内．

$$
(\alpha_0,-\alpha_1,\alpha_2,\cdots,(-1)^{n-1}\alpha_{n-1},0,\cdots)<(\beta_0,-\beta_1,\beta_2,\cdots,(-1)^{m-1}\beta_{m-1},0,\cdots).
$$

相较于连分数表示，交替地添加正负号，删去末尾的 $1$，并且长度不足的位置用 $0$ 补齐．

=== "C++"
    ```cpp
    --8<-- "docs/math/code/continued-fraction/compare.cpp:core"
    ```

=== "Python"
    ```py
    --8<-- "docs/math/code/continued-fraction/compare.py:core"
    ```

要构造出 $x\pm\varepsilon$，只需要在节点 $x$ 处首先向右（左）移动一次，再向左（右）移动 $\infty$ 次即可．转化成连分数的语言，对于分数 $x=[a_0,a_1,\cdots,a_{n-1},1]$，可以知道 $x\pm\varepsilon$ 必然是 $[a_0,a_1,\cdots,a_{n-1}+1,\infty]$ 和 $[a_0,a_1,\cdots,a_{n-1},1,\infty]$，因而只需要比较这两个连分数，将较大（小）的定义为 $x\pm\varepsilon$．

=== "C++"
    ```cpp
    --8<-- "docs/math/code/continued-fraction/inner-point.cpp:core"
    ```

=== "Python"
    ```py
    --8<-- "docs/math/code/continued-fraction/inner-point.py:core"
    ```

1.  $A_i,B_i>0$ 的情形可以忽略，因为已经假设 $(x,y)>0$；
2.  $A_i,B_i\le 0$ 的情形直接输出「IMPOSSIBLE」；
3.  $A_i>0,B_i\le 0$ 的情形相当于约束 $\dfrac{y}{x}<\dfrac{A_i}{-B_i}$；
4.  $A_i\le 0,B_i>0$ 的情形相当于约束 $\dfrac{y}{x}>\dfrac{-A_i}{B_i}$．

因此，取 $\dfrac{p_0}{q_0}$ 是第四种情形中最大的 $\dfrac{-A_i}{B_i}$，再取 $\dfrac{p_1}{q_1}$ 是第三种情形中最小的 $\dfrac{A_i}{-B_i}$．原问题就变成了找到字典序最小的 $(q,p)$ 使得 $\dfrac{p_0}{q_0}<\dfrac{p}{q}<\dfrac{p_1}{q_1}$ 成立．

=== "C++"
    ```cpp
    --8<-- "docs/math/code/continued-fraction/gcj-2019.cpp:core"
    ```

=== "Python"
    ```py
    --8<-- "docs/math/code/continued-fraction/gcj-2019.py:core"
    ```

$$
L(x) = \dfrac{ax+b}{cx+d},
$$

其中，$a,b,c,d\in\mathbf R$ 且 $ad-bc\neq 0$．

$$
M_i=\begin{pmatrix}a_i & b_i \\ c_i & d_i\end{pmatrix}
$$

则它们有如下性质：[^pgl2]

1.  分式线性变换的复合 $L_1\circ L_2$ 和逆变换 $L_1^{-1}$ 仍然是分式线性变换，即全体分式线性变换构成 [群](../algebra/basic.md#群)；
2.  分式线性变换在系数同乘以非零常数后保持不变，即对于任意 $\lambda\neq 0$，如果 $M_2=\lambda M_1$，则 $L_2=L_1$；
3.  分式线性变换的复合的系数矩阵，对应着系数矩阵的乘积，即如果 $M_1M_2=M_3$，则 $L_1\circ L_2=L_3$；
4.  分式线性变换的逆变换的系数矩阵，对应着系数矩阵的逆矩阵，即如果 $M_1^{-1}=M_2$，则 $L_1^{-1}=L_2$．

分式线性变换 $L_1$ 和 $L_2$ 的复合：

$$
\begin{aligned}
L_1\circ L_2 &= \dfrac{a_1\dfrac{a_2x+b_2}{c_2x+d_2}+b_1}{c_1\dfrac{a_2x+b_2}{c_2x+d_2}+d_1} = \dfrac{(a_1a_2+b_1c_2)x+(a_1b_2+b_1d_2)}{(c_1a_2+d_1c_2)x+(c_1b_2+d_1d_2)}.
\end{aligned}
$$

分式线性变换 $L_1(x)$ 的逆变换：

$$
y = L_1(x) = \dfrac{a_1x+b_1}{c_1x+d_1} \iff x = L_1^{-1}(y) = \dfrac{d_1y - b_1}{-c_1y + a_1}.
$$

=== "C++"
    ```cpp
    --8<-- "docs/math/code/continued-fraction/flt-presum.cpp"
    ```

=== "Python"
    ```py
    --8<-- "docs/math/code/continued-fraction/flt-presum.py"
    ```

$$
L_\gamma(x) = \gamma+\dfrac{1}{x} = \dfrac{\gamma x+1}{x}.
$$

因为连分数

$$
L(\alpha) = L\circ L_{\alpha_0}\circ L_{\alpha_1}\circ \cdots \circ L_{\alpha_n}(\infty),
$$

所以，可以向 $L$ 通过逐步复合 $L_{\alpha_k}$ 的方式计算 $L(\alpha)$ 的大小．但是，如果是希望得到 $L(\alpha)$ 的连分数表示，那么并不需要完全计算 $L(\alpha)$ 的值再求出连分数表示．可以在复合 $L_{\alpha_i}$ 的过程中就能判断 $\beta_0,\beta_1,\cdots$ 的值．

比如，假设当前计算到

$$
L\circ L_{\alpha_0}\circ L_{\alpha_1}\circ \cdots \circ L_{\alpha_k}(x) = \dfrac{a_kx+b_k}{c_kx+d_k}
$$

且 $c_k,d_k$ 同号．那么，$L\circ L_{\alpha_0}\circ L_{\alpha_1}\circ \cdots \circ L_{\alpha_k}(x)$ 在 $[0,\infty]$ 上单调，且必然取值在 $\dfrac{a_k}{c_k}$ 和 $\dfrac{b_k}{d_k}$ 之间．所以，如果

$$
\left\lfloor\dfrac{a_k}{c_k}\right\rfloor = \left\lfloor\dfrac{b_k}{d_k}\right\rfloor,
$$

就可以确定它就是 $L\circ L_{\alpha_0}\circ L_{\alpha_1}\circ \cdots \circ L_{\alpha_k}(x)$ 的整数部分 $\beta_0$．此时，在左侧复合 $L_{\beta_0}^{-1}$ 就可以得到

$$
L_{\beta_0}^{-1}\circ L\circ L_{\alpha_0}\circ L_{\alpha_1}\circ \cdots \circ L_{\alpha_k}.
$$

此时，继续添加 $L_{\alpha_{k+1}},L_{\alpha_{k+2}},\cdots$ 就可以确定新的整数部分，即 $\beta_1$．这样计算下去，直到确定出所有的 $\beta_j$ 的值．

算法要求 $c$ 和 $d$ 同号，是因为要保证函数的不连续点不在 $[0,\infty]$ 范围内．这总是可能的，因为简单连分数的定义要求（除了 $\alpha_0$ 外的）系数都是正整数．由此可以证明，必然在有限步内成立 $c$ 和 $d$ 同号，且将在之后一直保持同号．

具体实现时，只需要维护当前的分式线性变换的系数矩阵 $\begin{pmatrix}a&b\\c&d\end{pmatrix}$ 并检查 $c$ 和 $d$ 是否同号以及 $\dfrac{a}{c}$ 和 $\dfrac{b}{d}$ 是否有相同的整数部分．右复合 $L_{\alpha_i}$ 时，就可以得到 $\begin{pmatrix}a\alpha_i+b&a\\ c\alpha_i+d&c\end{pmatrix}$．如果两者整数部分相同为 $\beta_j$，则在结果的连分数内添加 $\beta_j$，并且左复合 $L_{\beta_j}^{-1}$，这相当于计算 $\begin{pmatrix}c&d\\ a\bmod c & b \bmod d \end{pmatrix}$．

$$
\left\lfloor\dfrac{a}{e}\right\rfloor = \left\lfloor\dfrac{b}{f}\right\rfloor = \left\lfloor\dfrac{c}{g}\right\rfloor = \left\lfloor\dfrac{d}{h}\right\rfloor.
$$

右复合要替换成计算 $L(x,y)\mapsto L(L_{\alpha_i}(x),y)$ 和 $L(x,y)\mapsto L(x,L_{\beta_j}(y))$，这同样表示成系数的线性变换．左复合则和单变量的情形完全一致，只需要计算取模就可以了．

相较于单变量的情形，双变量的情形需要决定要先复合 $L_{\alpha_i}$ 还是 $L_{\beta_j}$．因为复合的顺序与最后的结果无关，所以可以自由选择复合顺序，比如交替地复合 $L_{\alpha_i}$ 和 $L_{\beta_j}$．或者采用经验法则，优先复合比值差距更大的维度：如果 $\left|\dfrac{b}{f}-\dfrac{d}{h}\right|>\left|\dfrac{c}{g}-\dfrac{d}{h}\right|$，那么就先复合 $L_{\alpha_i}$；否则，就先复合 $L_{\beta_j}$．

$$
\begin{aligned}
x&=[a_0,\cdots,a_{k-1},y] = L_0(y),\\
y&=[a_k,\cdots,a_{k+L-1},y] = L_1(y),
\end{aligned}
$$

其中，$L_0(\cdot)$ 和 $L_1(\cdot)$ 都是分式线性变换．于是，得到 $x$ 满足的方程

$$
x = L_0\circ L_1\circ L_0^{-1}(x). 
$$

不妨设分式线性变换 $L_0\circ L_1\circ L_0^{-1}(x) = \dfrac{ax+b}{cx+d}$，则得到 $x$ 满足的方程

$$
cx^2+(d-a)x-b=0.
$$

因而，循环连分数都是整系数二次方程的解．又因为无限连分数都是无理数，所以循环连分数都表示了二次无理数．

$$
x = \dfrac{P_0+\sqrt{D}}{Q_0}
$$

的形式，其中，$P_0,Q_0,D$ 都是整数且 $Q_0\mid D-P_0^2$．这总是可能的，比如二次无理数 $x$ 总可以写成

$$
a+b\sqrt{D'} = \dfrac{p_a}{q_a}+\dfrac{p_b}{q_b}\sqrt{D'} = \dfrac{p_aq_b+p_bq_a\sqrt{D'}}{q_aq_b} = \dfrac{p_ap_bq_aq_b+\sqrt{(q_aq_b)^2D'}}{(q_aq_b)^2}
$$

再令 $P=p_ap_bq_aq_b$，$Q=(q_aq_b)^2$ 和 $D=QD'$ 即可．

将它写成这种形式的好处是，可以证明它的所有余项都具有类似的形式：

$$
r_k=\dfrac{P_k+\sqrt D}{Q_k},
$$

其中，$P_k,Q_k$ 是整数且 $Q_k\mid D-P_k^2$．其中，条件 $Q_k\mid D-P_k^2$ 保证了所有余项的分子中，$\sqrt{D}$ 前面的系数都是 $1$．

为得到余项的形式，可以使用数学归纳法．当 $k=0$ 时，显然．假设已经得到了 $r_k$ 的形式，并设 $a_k=\lfloor r_k\rfloor$，就有

$$
r_k = a_k+\dfrac{1}{r_{k+1}}.
$$

设 $r_{k+1}$ 也有类似形式，并和 $r_k$ 一起代入上式，有

$$
\dfrac{P_k+\sqrt D}{Q_k} = a_k + \dfrac{Q_{k+1}}{P_{k+1}+\sqrt{D}} = a_k + \dfrac{Q_{k+1}P_{k+1}-Q_{k+1}\sqrt{D}}{P_{k+1}^2-D}.
$$

因为二次无理数表示成 $a+b\sqrt{D}$ 的方式是唯一的，所以比较两侧系数可知

$$
\dfrac{P_k}{Q_k} = a_k+\dfrac{Q_{k+1}P_{k+1}}{P_{k+1}^2-D},\ \dfrac{1}{Q_k}=-\dfrac{Q_{k+1}}{P_{k+1}^2-D}.
$$

将第二个等式代入第一个等式可以解出 $P_{k+1}$：

$$
\dfrac{P_k}{Q_k} = a_k-\dfrac{P_{k+1}}{Q_k} \iff P_{k+1} = a_kQ_k-P_k.
$$

再代入第二个等式，就可以解出 $Q_{k+1}$：

$$
Q_{k+1} = \dfrac{D-P_{k+1}^2}{Q_k} = \dfrac{D-(a_kQ_k-P_k)^2}{Q_k} = -a_k^2Q_k+2a_kP_k+\dfrac{D-P_k^2}{Q_k}.
$$

根据归纳假设，$Q_k\mid D-P_k^2$，所以确实 $P_{k+1}$ 和 $Q_{k+1}$ 都是整数，即 $r_{k+1}$ 也具有所要求的形式．

最后，证明余项只能取得有限多个值，故而必然重复．前文已经求得余项

$$
\dfrac{P_k+\sqrt{D}}{Q_k} = r_k = -\dfrac{q_{k-2}x-p_{k-2}}{q_{k-1}x-p_{k-1}}
$$

而且对于无理数，总有 $r_k>1$．同时，它的共轭

$$
\dfrac{P_k-\sqrt{D}}{Q_k} = r_k^* = -\dfrac{q_{k-2}x^*-p_{k-2}}{q_{k-1}x^*-p_{k-1}} = -\dfrac{q_{k-2}}{q_{k-1}}\dfrac{x^*-\dfrac{p_{k-2}}{q_{k-2}}}{x^*-\dfrac{p_{k-1}}{q_{k-1}}}
$$

对于充分大的 $k$ 必然小于 $0$，因为

$$
\dfrac{q_{k-2}}{q_{k-1}}>0,\ \lim_{k\rightarrow\infty}\dfrac{x^*-\dfrac{p_{k-2}}{q_{k-2}}}{x^*-\dfrac{p_{k-1}}{q_{k-1}}}=\dfrac{x^*-x}{x^*-x}=1.
$$

这就说明

$$
\dfrac{2\sqrt{D}}{Q_k} = r_k-r_k^*>1 \iff 0<Q_k\le 2\sqrt{D}.
$$

因此，$Q_k$ 只能取有限多个值．进而，

$$
D-P_{k}^2=Q_kQ_{k-1}>0 \iff |P_k|<\sqrt{D},
$$

所以，$P_k$ 也只能取有限多个值．故而，余项 $r_k$ 只有有限多个可能的取值，必然在无限项内重复．

$$
x=\dfrac{P_0+\sqrt{D}}{Q_0}
$$

的形式，且 $Q_0\mid D-P^2_0$．它的余项

$$
r_{k}=\dfrac{P_k+\sqrt{D}}{Q_k}
$$

中，$P_k,Q_k$ 都是整数，且满足递推关系

$$
\begin{aligned}
P_{k+1} &= a_kQ_k-P_k,\\
Q_{k+1} &= \dfrac{D-P_{k+1}^2}{Q_k}.
\end{aligned}
$$

=== "C++"
    ```cpp
    --8<-- "docs/math/code/continued-fraction/quadratic-irrational.cpp:core"
    ```

=== "Python"
    ```py
    --8<-- "docs/math/code/continued-fraction/quadratic-irrational.py:core"
    ```

=== "C++"
    ```cpp
    --8<-- "docs/math/code/continued-fraction/surd-convergent.cpp"
    ```

=== "Python"
    ```py
    --8<-- "docs/math/code/continued-fraction/surd-convergent.py"
    ```

$$
x = \left[\overline{a_0,a_1,\cdots,a_{\ell}}\right],
$$

记

$$
x' = \left[\overline{a_{\ell},\cdots,a_1,a_0}\right].
$$

则 $x$ 和 $x'$ 互为「倒数负共轭」，即 $x$ 的共轭的倒数的相反数是 $x'$．

$$
\begin{aligned}
\dfrac{p_\ell}{p_{\ell-1}} &= [a_\ell,\cdots,a_1,a_0] = \dfrac{p'_\ell}{q'_\ell},\\
\dfrac{q_\ell}{q_{\ell-1}} &= [a_\ell,\cdots,a_1] = \dfrac{p'_{\ell-1}}{q'_{\ell-1}}.
\end{aligned}
$$

因为等式两侧都是既约分数，所以

$$
p'_\ell = p_\ell,\ q'_\ell = p_{\ell-1},\ p'_{\ell-1}=q_\ell,\ q'_{\ell-1} = q_{\ell-1}.
$$

对于纯循环连分数 $x$，它的第 $\ell+1$ 个余项就是 $x$，因此，有

$$
x = \dfrac{xp_\ell+p_{\ell-1}}{xq_\ell+q_{\ell-1}}.
$$

所以，它满足二次方程

$$
q_\ell x^2+(q_{\ell-1}-p_\ell)x-p_{\ell-1} = 0.
$$

同理，$x'$ 满足二次方程

$$
q'_\ell(x')^2+(q'_{\ell-1}-p'_\ell)x'-p'_{\ell-1} = 0.
$$

利用系数的关系可知，这个方程可以写作

$$
p_{\ell-1}(x')^2+(q_{\ell-1}-p_\ell)x'-q_\ell = 0.
$$

令 $y=-\dfrac{1}{x'}$，则 $x$ 和 $y$ 满足同一个方程．但是，$x>0>y$，因此它们并非同一个根，而是互为共轭的关系，这就证明了原命题．

反过来，设二次无理数 $x>1$ 且 $-1<x^*<0$．对于 $x$ 的余项 $r_k$，有递推关系

$$
r_k = a_k+\dfrac{1}{r_{k+1}}.
$$

等式两边都是二次无理数，取共轭可知

$$
r_{k}^* = a_k+\dfrac{1}{r_{k+1}^*}.
$$

利用这个递推关系，可以证明 $-1<r_{k}^*<0$ 对所有 $k\ge 0$ 都成立．

首先，对于 $k=0$，有 $-1<r_0^*=x_0^*<0$，显然．对于 $k\ge 0$，由简单连分数定义和 $x>1$ 可知，$a_k\ge 1$．故而，假设 $-1<r_k^*<0$，就有

$$
-1<-\dfrac{1}{a_k}< r_{k+1}^* = \dfrac{1}{r_k^*-a_k} < -\dfrac{1}{1+a_k} < 0.
$$

这就归纳地证明了 $-1<r_{k}^*<0$ 对所有 $k\ge 0$ 都成立．因此，有

$$
a_k = -\dfrac{1}{r_{k+1}^*}+r_k^* = \left\lfloor-\dfrac{1}{r_{k+1}^*}\right\rfloor.
$$

因为二次无理数一定是循环连分数，所以存在正整数 $L$ 和至少某个充分大的 $k$，有 $r_{k}=r_{k+L}$．但是，此时必然也有

$$
a_{k-1} = \left\lfloor-\dfrac{1}{r_{k}^*}\right\rfloor = \left\lfloor-\dfrac{1}{r_{k+L}^*}\right\rfloor = a_{k+L-1}.
$$

故而，

$$
r_{k-1} = a_{k-1}+\dfrac{1}{r_k} = a_{k+L-1}+\dfrac{1}{r_{k+L}} = r_{k+L-1}.
$$

这意味着最小的能够使得 $r_{k}=r_{k+L}$ 成立的 $k$ 必然是 $0$．也就是说，$x$ 可以表示成纯循环连分数．

$$
\sqrt{r} = [\lfloor\sqrt{r}\rfloor,\overline{a_1,\cdots,a_{\ell},2\lfloor\sqrt{r}\rfloor}]
$$

且对于任意 $1\le k\le\ell$，都有 $a_k = a_{\ell+1-k}$．

$$
\lfloor\sqrt{r}\rfloor+\sqrt{r} = [\overline{2\lfloor\sqrt{r}\rfloor,a_1,\cdots,a_\ell}].
$$

根据上述定理，它的倒数负共轭具有形式

$$
\dfrac{1}{\sqrt{r}-\lfloor\sqrt{r}\rfloor} = [\overline{a_\ell,\cdots,a_1,2\lfloor\sqrt{r}\rfloor}].
$$

利用连分数的基本性质可知

$$
\sqrt{r}=\lfloor\sqrt{r}\rfloor+\dfrac{1}{\dfrac{1}{\sqrt{r}-\lfloor\sqrt{r}\rfloor}}=[\lfloor\sqrt{r}\rfloor,\overline{a_\ell,\cdots,a_1,2\lfloor\sqrt{r}\rfloor}].
$$

但是，又由 $\lfloor\sqrt{r}\rfloor+\sqrt{r}$ 的连分数表示可知，

$$
\sqrt{r} = -\lfloor\sqrt{r}\rfloor+\left(\lfloor\sqrt{r}\rfloor+\sqrt{r}\right) = [\lfloor\sqrt{r}\rfloor,\overline{a_1,\cdots,a_\ell,2\lfloor\sqrt{r}\rfloor}].
$$

因为无理数的连分数表示是唯一的，所以比较中间的系数就知道，$a_k=a_{\ell+1-k}$ 对所有 $1\le k\le\ell$ 都成立．

$$
\begin{aligned}
\sqrt{74}&=8+(-8)+\sqrt{74}=\left[8,\frac{8+\sqrt{74}}{10}\right]\\
&=\left[8,1+\frac{-2+\sqrt{74}}{10}\right]=\left[8,1,\frac{2+\sqrt{74}}{7}\right]\\
&=\left[8,1,1+\frac{-5+\sqrt{74}}{7}\right]=\left[8,1,1,\frac{5+\sqrt{74}}{7}\right]\\
&=\left[8,1,1,1+\frac{-2+\sqrt{74}}{7}\right]=\left[8,1,1,1,\frac{2+\sqrt{74}}{10}\right]\\
&=\left[8,1,1,1,1+\frac{-8+\sqrt{74}}{10}\right]=\left[8,1,1,1,1,8+\sqrt{74}\right]\\
&=\left[8,1,1,1,1,16+(-8)+\sqrt{74}\right]=\left[8,\overline{1,1,1,1,16}\right]
\end{aligned}
$$

各个余项分别是：

$$
\begin{alignedat}{3}
r_1&=\frac{8+\sqrt{74}}{10}&&=\left[\overline{1,1,1,1,16}\right]\\
r_2&=\frac{2+\sqrt{74}}{7}&&=\left[\overline{1,1,1,16,1}\right]\\
r_3&=\frac{5+\sqrt{74}}{7}&&=\left[\overline{1,1,16,1,1}\right]\\
r_4&=\frac{2+\sqrt{74}}{10}&&=\left[\overline{1,16,1,1,1}\right]\\
r_5&=8+\sqrt{74}&&=\left[\overline{16,1,1,1,1}\right]
\end{alignedat}
$$

根据 Galois 的结论，余项 $r_k$ 和 $r_{L+1-k}$ 循环部分恰好相反，因此互为倒数负共轭．如果 $\sqrt{D}$ 的循环节长度 $L$ 为奇数，那么中间的一项就与自身互为倒数负共轭；如果循环节长度 $L$ 为偶数，就不存在这样的项．Pell 方程一节的讨论会说明，循环节长度的奇偶性将决定了方程 $x^2-Dy^2=-1$ 是否有解．

![](./images/lattice-hull.svg)

从 $(0,0)$ 开始，可以自左向右地求出上凸壳的所有整点．假设当前已经求出的上凸壳的最后一个整点是 $(x,y)$．现在要求出下一个��点 $(x',y')$．顶点 $(x',y')$ 在 $(x,y)$ 右上方，记 $(\Delta x,\Delta y)=(x'-x,y'-y)$ 为两者的差值．那么，必然有

$$
0<\Delta x\le N-x,\ 0\le \Delta y\le r\Delta x.
$$

第二个不等式成立，因为条件 $\Delta y>r\Delta x$ 与 $(x,y)$ 已经在上凸壳上这件事矛盾．观察 $(\Delta x,\Delta y)$ 需要满足的条件，对于不同的点 $(x,y)$，只有 $\Delta x$ 的上界在变化．所以，只要能解决这个子问题，就可以递归地求出原问题的所有整点．

进而，考虑子问题的解法．对比于原问题，子问题相当于将 $x$ 的上界修改为 $N'$，并求出上凸壳中与原点相邻的第一个整点．记子问题的解为 $(q,p)$．那么，$p$ 与 $q$ 必然是互素的（否则不是第一个整点），且与原点连线的斜率 $\dfrac{p}{q}$ 是所有位于直线 $y=rx$ 下方且横坐标不超过 $N'$ 的整点中最大的（否则不在凸包上）．结合前文的 [几何解释](#几何解释) 可知，这样的点 $(x,y)$ 必然对应于 $r$ 的一个下中间分数．因为分母越大的下中间分数离 $r$ 越近，所以子问题的解 $(q,p)$ 对应着所有分母不超过 $N'$ 的下中间分数中分母最大的那个．

当然，实际求解时，没必要对每个子问题都重新求出这样的下中间分数．应该首先求出所有的渐近分数，这相当于提供了遍历所有的下中间分数的方法．然后分母从大到小地遍历下中间分数，每次都尝试将它加到前一个整点 $(x,y)$ 上，直到不能添加为止才继续尝试下一个下中间分数．

此处有一些显然的优化．首先，对于下中间分数 $(q,p)$，必然存在奇数 $k$ 和 $0\le t<a_k$ 使得 $(q,p)=(q_{k-1},p_{k-1})+t(q_k,p_k)$．只要找到最大的 $t$ 使得 $q_{k-1}+tq_k+x\le N$ 满足就好了，亦即 $t=\left\lfloor\dfrac{N-q_{k-1}-x}{q_k}\right\rfloor$．不用担心 $t$ 越界，因为更大的下渐近分数 $(q_{k+2},p_{k+2})$ 已经添加完了．而每次确定添加的次数的时候，直接计算 $\left\lfloor\dfrac{N-x}{q}\right\rfloor$ 即可，不必逐个尝试．

优化后的算法的复杂度是 $O(n)$ 的．虽然下中间分数对应的整点可能有很多，但是真正成为增量的并不多．下面要说明，所有 $0\le t<a_k$ 的下中间分数 $(q,p)=(q_{k-1},p_{k-1})+t(q_k,p_k)$ 中，至多会出现两个增量．假设这些下中间分数中确实出现了增量，则此时必然有 $q_{k-1}\le N-x<q_{k+1}$．不妨设 $t=\left\lfloor\dfrac{N-q_{k-1}-x}{q_k}\right\rfloor$．如果 $t=0$，则增量就有 $\Delta x=q_{k-1}$，故而添加完增量后，就有 $N-x'<q_{k-1}$，不会再在这些下中间分数中出现新的增量；如果 $t>0$，那么添加完增量后，必然有 $N-x'=(N-q_{k-1}-x)\bmod q_k<q_k$，即使还会在同一段下中间分数中出现新的增量，下次也只能有 $t'=0$．因此，在这样的一段下中间分数中，至多只能出现两个增量．这就说明，总的时间复杂度是 $O(n)$ 的．

=== "C++"
    ```cpp
    --8<-- "docs/math/code/continued-fraction/hull-under-line.cpp:core"
    ```

=== "Python"
    ```py
    --8<-- "docs/math/code/continued-fraction/hull-under-line.py:core"
    ```

为了讨论方便，首先通过代换 $x\mapsto\left\lfloor N/A\right\rfloor-x$ 来改变 $x$ 的符号．令 $C=N\bmod A$ 和 $M=\left\lfloor N/A\right\rfloor$，则原问题转化为在 $0\le x\le M$ 且 $By-Ax\le C$ 的条件下，求最优的 $(x,y)$ 使得 $By-Ax$ 最大．对于每个固定的 $x$，最优的 $y$ 的取值为 $\left\lfloor\dfrac{Ax+C}{B}\right\rfloor$．

接下来要说明的是，这个问题和上一个例题具有类似的解法．但是，与上一个例题中使用下中间分数偏离直线不同，本题需要使用上中间分数来接近直线．具体来说，$C-(By-Ax)$ 的值正比于点 $(x,y)$ 与直线 $By-Ax=C$ 的距离．要最大化 $By-Ax$，就等价于最小化这个距离．算法的目标是要找到直线 $By-Ax=C$ 下方距离它最近的可行的整点．算法的思路就是从最左侧的点开始，沿着这些整点的上凸壳搜索，逐步缩小与直线的距离，直到得到最优解．

在 $(x,y)$ 的坐标系内，算法从 $(0,\lfloor C/B\rfloor)$ 出发，递归地寻找并添加最优的增量 $(\Delta x,\Delta y)$，且保证添加后的点比起之前更靠近直线 $By-Ax=C$，但是不能到达直线的另一侧，也不能让横坐标大于 $M$．设已经得到的点是 $(x,y)$，那么增量 $(\Delta x,\Delta y)$ 满足的条件就是

$$
0<B\Delta y-A\Delta x\le C-(By-Ax),\ 0<\Delta x\le M-x.
$$

按照沿下凸壳搜索的思路，只需要找到满足这些条件的点中 $\Delta x$ 最小的即可．将第一个不等式改写成

$$
\Delta y \le \dfrac{A}{B}\Delta x+\dfrac{C-(By-Ax)}{B}.
$$

结合前文的 [几何解释](#几何解释) 可知，只要后面的常数项小于 $1$，那么满足这个不等式的整点 $(\Delta x,\Delta y)$ 中横坐标最小的，一定对应着某个上中间分数．这是因为它是所有分母不超过它的分母的分数中，从上方逼近某个实数效果最好的，这只能是上中间分数．而每次添加增量后，都会导致 $\Delta y$ 的上界变得更紧，这意味着必须考察分母更大的上中间分数．

仿照上一个例题的思路．分母从小到大考察所有上中间分数，如果能够找到横坐标和纵坐标都不越界的上中间分数，就添加进去，并更新相应的上界．当所有可行的上中间分数都添加结束后，得到的就是最优解．相较于之前，这个题目需要同时保证横纵坐标都不越界，需要格外注意．基于和上一个例题类似的论述，不过这次是使用 $B\Delta y-A\Delta x$ 代替之前的 $\Delta x$，可以说明这个算法的复杂度是 $O(\log\min\{A,B\})$ 的．

=== "C++"
    ```py
    --8<-- "docs/math/code/continued-fraction/closest-dio.cpp:core"
    ```

=== "Python"
    ```py
    --8<-- "docs/math/code/continued-fraction/closest-dio.py:core"
    ```

提示：$e = [2,1,2,1,1,4,1,1,6,1,\cdots,1,2n,1, \cdots]$．[^continued-fraction-of-e]

原问题要求 $N \le 10^{4000}$．此处 C++ 代码仅作示意，并没有实现高精度计算类．

=== "C++"
    ```cpp
    --8<-- "docs/math/code/continued-fraction/sum-floor.cpp:core"
    ```

=== "Python"
    ```py
    --8<-- "docs/math/code/continued-fraction/sum-floor.py:core"
    ```

$$
\sum_{i=1}^n [pi \bmod q] 
=\sum_{i=1}^n\left(pi - q\left\lfloor\dfrac{pi}{q}\right\rfloor\right) = \dfrac{pn(n+1)}{2} - q\sum_{i=1}^n\left\lfloor\dfrac{p}{q}i\right\rfloor,
$$

这个问题可以转化为上一个问题，只要用 $\dfrac{p}{q}$ 替代 $\mathrm{e}$ 即可．单次查询的时间复杂度为 $O(\log\min\{p,q\})$．

=== "C++"
    ```cpp
    --8<-- "docs/math/code/continued-fraction/mod-mod-mod.cpp:core"
    ```

=== "Python"
    ```py
    --8<-- "docs/math/code/continued-fraction/mod-mod-mod.py:core"
    ```

可以通过构造直线 $y=\dfrac{Ax+B}{M}$ 以下且 $0\le x< N$ 的全部整点的凸包，并用 Pick 定理计算整点的个数．之前已经解决 $B=0$ 的情形．对于一般的情形，可以分为两步进行．首先通过添加上中间分数来逐步接近直线（即第二个例题），直到找到最接近直线的点，再通过添加下中间分数来逐步远离直线（即第一个例题）．

=== "C++"
    ```py
    --8<-- "docs/math/code/continued-fraction/sum-floor-axbc.cpp:core"
    ```

=== "Python"
    ```py
    --8<-- "docs/math/code/continued-fraction/sum-floor-axbc.py:core"
    ```

这个问题等价于找到 $[1,N]$ 中使得 $Ax\bmod M$ 最小的 $x$．

对于某个模数 $m$，使得 $qr\equiv p\pmod m$ 成立的数对 $(p,q)$ 可能并不唯一．假设 $(p_1,q_1)$ 和 $(p_2,q_2)$ 都可以使得这个等式成立，那么必然有 $(p_1q_2-p_2q_1)r\equiv 0\pmod m$．根据 $r$ 的构造可知，$r$ 与 $m$ 互素，所以 $p_1q_2-p_2q_1\equiv 0\pmod m$，亦即 $m\mid(p_1q_2-p_2q_1)$．如果 $p_1q_2-p_2q_1$ 不为零，那么它的绝对值至少是 $m$．问题中限制了 $p,q\in[1,10^9]$，这意味着这个差值不应该超过 $10^{18}$，因此只要取 $m>10^{18}$ 就可以保证求出的 $(p,q)$ 是唯一的．

现在的问题归结为，给定模数 $m$ 和余数 $r$，求不超过 $n$ 的正整数对 $(p,q)$ 使得 $qr\equiv p\pmod m$．在已知这样的解是唯一的情况下，其实只要找到 $q\in[1,n]$ 时使得 $qr\bmod m$ 最小的 $q$ 即可，因为此时有且仅有一个 $q$ 使得余数不超过 $n$．这正是前面提到的等价表述．

在 $(q,k)$ 所在的平面坐标系内，这相当于要找到 $q\in[1,n]$ 时在直线 $qr-km=0$ 下方最接近它的整点，因为余数 $qr\bmod m$ 就正比于整点与直线的距离．结合前文的 [几何解释](#几何解释) 可知，这样的整点必然对应着有理分数 $\dfrac{r}{m}$ 的某个下中间分数．算法复杂度是 $O(\log\min\{r,m\})$．

=== "C++"
    ```cpp
    --8<-- "docs/math/code/continued-fraction/recover-fraction.cpp:core"
    ```

=== "Python"
    ```py
    --8<-- "docs/math/code/continued-fraction/recover-fraction.py:core"
    ```