循環連分數

線性分式變換

連分數的另一個重要概念是所謂的線性分式變換（Linear fractional transformations）。

定義

線性分式變換 是一個函數 \(f : \mathbb R \to \mathbb R\)，使得 \(f(x) = \frac{ax+b}{cx+d}\) 對於一些 \(a,b,c,d \in \mathbb R\)。

線性分式變換 \(L_0(x)=\frac{a_0 x + b_0}{c_0 x + d_0}\) 和 \(L_1(x)=\frac{a_1 x + b_1}{c_1 x + d_1}\) 的組合 \((L_0 \circ L_1)(x) = L_0(L_1(x))\) 也是線性分式變換：

\[ \frac{a_0\frac{a_1 x + b_1}{c_1 x + d_1} + b_0}{c_0 \frac{a_1 x + b_1}{c_1 x + d_1} + d_0} = \frac{a_0(a_1 x + b_1) + b_0 (c_1 x + d_1)}{c_0 (a_1 x + b_1) + d_0 (c_1 x + d_1)} = \frac{(a_0 a_1 + b_0 c_1) x + (a_0 b_1 + b_0 d_1)}{(c_0 a_1 + d_0 c_1) x + (c_0 b_1 + d_0 d_1)} \]

線性分式變換的逆，也是線性分式變換：

\[ y = \frac{ax+b}{cx+d} \iff y(cx+d) = ax + b \iff x = -\frac{dy-b}{cy-a} \]

DMOPC '19 Contest 7 P4 - Bob and Continued Fractions

給您一個正整數數組 \(a_1, \dots, a_n\)。您需要回答 \(m\) 查詢。每個查詢都要計算 \([a_l; a_{l+1}, \dots, a_r]\)。

解答

如果能夠連接連分數，則可以用線段樹來解決這個問題。

通常情況下，\([a_0; a_1, \dots, a_k, b_0, b_1, \dots, b_k] = [a_0; a_1, \dots, a_k, [b_1; b_2, \dots, b_k]]\) 是正確的。

表示 \(L_{k}(x) = [a_k; x] = a_k + \frac{1}{x} = \frac{a_k\cdot x+1}{1\cdot x + 0}\)。注意 \(L_k(\infty) = a_k\)。在這個概念中，它認為

\[ [a_0; a_1, \dots, a_k, x] = [a_0; [a_1; [\dots; [a_k; x]]]] = (L_0 \circ L_1 \circ \dots \circ L_k)(x) = \frac{p_k x + p_{k-1}}{q_k x + q_{k-1}} \]

因此，問題歸結為計算

\[ (L_l \circ L_{l+1} \circ \dots \circ L_r)(\infty) \]

變換的組合是關聯的，因此可以在線段樹的每個節點中計算其子樹中變換的組合。

例題 連分數的線性分式變換

設 \(L(x) = \frac{ax+b}{cx+d}\)。對於 \(A=[a_0; a_1, \dots, a_n]\)，計算 \(L(A)\) 的連分數表示 \([b_0; b_1, \dots, b_m]\)。

從而，對任意的 \(\frac{p}{q}\)，可以計算 \(A + \frac{p}{q} = \frac{qA + p}{q}\) 和 \(A \cdot \frac{p}{q} = \frac{p A}{q}\)。

解答

如上所述，\([a_0; a_1, \dots, a_k] = (L_{a_0} \circ L_{a_1} \circ \dots \circ L_{a_k})(\infty)\)，因此 \(L([a_0; a_1, \dots, a_k]) = (L \circ L_{a_0} \circ L_{a_1} \circ \dots L_{a_k})(\infty)\)。

因此，通過依次添加 \(L_{a_0}\),\(L_{a_1}\) 等，可以計算

\[ (L \circ L_{a_0} \circ \dots \circ L_{a_k})(x) = L\left(\frac{p_k x + p_{k-1}}{q_k x + q_{k-1}}\right)=\frac{a_k x + b_k}{c_k x + d_k} \]

由於 \(L(x)\) 是可逆的，因此在 \(x\) 中也是單調的。因此，對於任何 \(x \geq 0\)，都有 \(L(\frac{p_k x + p_{k-1}}{q_k x + q_{k-1}})\) 介於 \(L(\frac{p_k}{q_k}) = \frac{a_k}{c_k}\) 和 \(L(\frac{p_{k-1}}{q_{k-1}}) = \frac{b_k}{d_k}\) 之間。

此外，對於 \(x=[a_{k+1}; \dots, a_n]\)，它等於 \(L(A)\)。因此，\(b_0 = \lfloor L(A) \rfloor\) 介於 \(\lfloor L(\frac{p_k}{q_k}) \rfloor\) 和 \(\lfloor L(\frac{p_{k-1}}{q_{k-1}}) \rfloor\) 之間。當它們相等時，它們也等於 \(b_0\)。

請注意，\(L(A) = (L_{b_0} \circ L_{b_1} \circ \dots \circ L_{b_m})(\infty)\)。知道 \(b_0\) 後，可以用當前變換合成 \(L_{b_0}^{-1}\)，並繼續添加 \(L_{a_{k+1}}\)、\(L_{a_{k+2}}\) 等，尋找新的下界（floor）以達成一致，從中可以推斷 \(b_1\) 等，直到恢復 \([b_0; b_1, \dots, b_m]\) 的所有值。

例題 連分數算法

令 \(A=[a_0; a_1, \dots, a_n]\)，\(B=[b_0; b_1, \dots, b_m]\)。計算 \(A+B\) 和 \(A \cdot B\) 的連分數表示。

解答

這裏的想法與前面的問題類似，但不應使用 \(L(x) = \frac{ax+b}{cx+d}\)，而應考慮雙線性分數變換 \(L(x, y) = \frac{axy+bx+cy+d}{exy+fx+gy+h}\)。

您可以將當前變換更改為 \(L(x, y) \mapsto L(L_{a_k}(x), y)\) 或 \(L(x, y) \mapsto L(x, L_{b_k}(y))\)，而不是 \(L(x) \mapsto L(L_{a_k}(x))\)。

然後，檢查 \(\lfloor \frac{a}{e} \rfloor = \lfloor \frac{b}{f} \rfloor = \lfloor \frac{c}{g} \rfloor = \lfloor \frac{d}{h} \rfloor\)，如果它們都一致，則在生成的分數中使用該值作為 \(c_k\)，並將轉換更改為

\[ L(x, y) \mapsto \frac{1}{L(x, y) - c_k} \]

循環連分數

仿照循環小數的概念，如果在連分數後面形成了循環，則形成 循環連分數。

循環連分數的最小正週期一般用字母 \(l\) 來表示，循環的部分稱為循環節。容易發現，進入循環的充要條件是餘項 \(r_k\) 的重複出現。

純循環連分數

定義

如果存在 \(k\) 使得 \(x = [a_0; a_1, \dots, a_k, x]\)，則連分數 \(x = [a_0; a_1, \dots]\) 被稱為 純循環（periodic）。

如果 \(x = [a_0; a_1, \dots, a_k, y]\)，其中 \(y\) 是純循環，則連分數 \(x = [a_0; a_1, \dots]\) 被稱為 混循環（eventually periodic）。

例如純循環連分數：

\([a_0,a_1,a_2,a_3,a_0,a_1,a_2,a_3,…]=[\overline{a_0,a_1,a_2,a_3}]\)

混循環連分數：

\([a_0,a_1,a_2,a_3,a_1,a_2,a_3,…]=[a_0,\overline{a_1,a_2,a_3}]\)

混循環連分數後面循環的部分，最早循環的部分稱為它的「純循環部分」。

純循環連分數的整數部分 \(a_0\) 直接進入到了循環裏面，因此要求 \(a_0\) 必須至少是 1。因此，純循環連分數大於 1。

對於 \(x = [1; 1, 1, \dots]\)，有 \(x = 1 + \frac{1}{x}\)，因此 \(x^2 = x + 1\)。在循環連分數和二次方程之間存在着一般的聯繫。考慮以下等式：

\[ x = [a_0; a_1, \dots, a_k, x] \]

一方面，這個方程意味着 \(x\) 的連分數表示是週期為 \(k+1\)。

另一方面，使用漸進分數的公式，這個方程意味着

\[ x = \frac{p_k x + p_{k-1}}{q_k x + q_{k-1}} \]

也就是説，\(x\) 是其自身的線性分數變換。從等式中可以看出，\(x\) 是二次方程式的根：

\[ q_k x^2 + (q_{k-1}-p_k)x - p_{k-1} = 0 \]

類似的推理代表了混循環連分數，即 \(x = [a_0; a_1, \dots, a_k, y]\) 代表 \(y=[b_0; b_1, \dots, b_k, y]\)。事實上，從第一個方程導出 \(x = L_0(y)\)，從第二個方程導出 \(y = L_1(y)\)，其中 \(L_0\) 和 \(L_1\) 是線性分數變換。因此

\[ x = (L_0 \circ L_1)(y) = (L_0 \circ L_1 \circ L_0^{-1})(x) \]

可以進一步證明（由拉格朗日首先完成），對於具有整數係數的任意二次方程 \(ax^2+bx+c=0\)，其解 \(x\) 是一個混循環連分數。

拉格朗日連分數定理

關於循環連分數有一個特別重要的基礎定理：

拉格朗日連分數定理：實二次有理數與循環連分數一一對應。

該定理最早由拉格朗日（Lagrange）於 1769 年證明。

根據餘項的重複出現，證明循環連分數一定是二次有理數非常容易。重點在於證明二次有理數一定是循環連分數。

證明

對二次有理數執行「無限簡單連分數」計算，即取倒數、取整交替，得到的餘數還是二次有理數。

接下來要強行刻畫餘項，將餘項束縛在有限的範圍，有限範圍裏的無限餘項必然會發生重複。

設 \(\xi\) 是如下形式的二次有理數：

\(\frac{1}{q}\left(c+\sqrt{d}\right)\quad q|N(c-\sqrt{d})\)

如果分母不整除分子的範數，那麼分子分母同時乘以分母的絕對值，並強行壓入根號，在新二次有理數中，分母整除新的分子的範數。因此，任何二次有理數都能寫成這形式。

根據上文的簡單連分數算法：對餘數取整可以得到 \(a\)，進而得到新的 \(c\)。

\(a_k=\frac{c_{k+1}+c_k}{q_k}\)

取整後得到的新的 \(c\) 為負數，且絕對值一定比 \(\sqrt{d}\) 小，因此範數為負。取倒數，得到新的分母 \(q\)，\(q\) 總是正的。

\(q_k q_{k+1}=-N(c_{k+1}-\sqrt{d})\)

由於範數為負，取倒數之後 \(\sqrt{d}\) 前面的符號不變，而 \(c\) 的符號由負變正（負數前面加負號變為正數）。

餘數 \(r\) 裏面，每個 \(c\) 都為負數，且絕對值一定比 \(\sqrt{d}\) 小，因此分子 \(c\) 的個數有限。

每個 \(q\) 都整除對應 \(c\) 構成二次整數的範數，因此分母 \(q\) 的個數有限。餘數有限必重複，至此證完。

例題 二次有理數

找到 \(\alpha = \frac{x+y\sqrt{n}}{z}\) 的連分數，其中 \(x, y, z, n \in \mathbb Z\) 和 \(n > 0\) 不是完全平方。

解答

對於數字的第 \(k\) 個完全商 \(s_k\)，通常認為

\[ \alpha = [a_0; a_1, \dots, a_{k-1}, s_k] = \frac{s_k p_{k-1} + p_{k-2}}{s_k q_{k-1} + q_{k-2}} \]

從而，

\[ s_k = -\frac{\alpha q_{k-1} - p_{k-1}}{\alpha q_k - p_k} = -\frac{q_{k-1} y \sqrt n + (x q_{k-1} - z p_{k-1})}{q_k y \sqrt n + (xq_k-zp_k)} \]

將分子和分母乘以 \((xq_k - zp_k) - q_k y \sqrt n\)，將去掉分母中的 \(\sqrt n\)，因此完全商為

\[ s_k = \frac{x_k + y_k \sqrt n}{z_k} \]

接下來求解 \(s_{k+1}\)，假設 \(s_k\) 是已知的。

首先，\(a_k = \lfloor s_k \rfloor = \left\lfloor \frac{x_k + y_k \lfloor \sqrt n \rfloor}{z_k} \right\rfloor\)。然後

\[ s_{k+1} = \frac{1}{s_k-a_k} = \frac{z_k}{(x_k - z_k a_k) + y_k \sqrt n} = \frac{z_k (x_k - y_k a_k) - y_k z_k \sqrt n}{(x_k - y_k a_k)^2 - y_k^2 n} \]

因此，如果表示 \(t_k = x_k - y_k a_k\)，將有

\[ \begin{align} x*{k+1} &=& z_k t_k \\ y*{k+1} &=& -y*k z_k \\ z*{k+1} &=& t_k^2 - y_k^2 n \end{align} \]

這種表示法的優點在於，如果將 \(x_{k+1}, y_{k+1}, z_{k+1}\) 減去它們的最大公約數，結果將是唯一的。因此，可以使用它來檢查當前狀態是否已經重複，以及檢查具有此狀態的上一個索引的位置。

下面是計算 \(\alpha = \sqrt n\) 的連分數表示的代碼：

Python

# compute the continued fraction of sqrt(n)
def sqrt(n):
    n0 = math.floor(math.sqrt(n))
    x, y, z = 0, 1, 1
    a = []
    def step(x, y, z):
        a.append((x * n0 + y) // z)
        t = y - a[-1]*z
        x, y, z = z*t, -z*y, t**2 - n*x**2
        g = math.gcd(x, math.gcd(y, z))
        return x // g, y // g, z // g

    used = dict()
    for i in range(n):
        used[x, y, z] = i
        x, y, z = step(x, y, z)
        if (x, y, z) in used:
            return a

使用相同的「step」函數，但不同的初始 \(x\),\(y\) 和 \(z\)，可以計算任意 \(\frac{x+y \sqrt{n}}{z}\)。

伽羅瓦連分數定理

純循環連分數有類似於反序定理的定理。記：

\[ x=\left[\overline{a_0,a_1,\ldots,a_{l-1}}\right] \]

\[ x'=\left[\overline{a_{l-1},a_{l-2},\ldots,a_0}\right] \]

則兩個 x 互為「倒數負共軛」。即，若記：

\[ y=-\frac{1}{x'} \]

則 x 與 y 共軛。

該定理最早由伽羅瓦（Galois）在他 17 歲那年（1828 年）發現並證明。

證明

不妨改取比較長（例如至少有 5 項）的循環節。將循環節部分反序，根據反序定理，漸進分數有：

\[ \frac{p_{l-1}}{p_{l-2}}=[a_{l-1},a_{l-2},\ldots,a_0]=\frac{{p'}_{l-1}}{{q'}_{l-1}} \]

\[ \frac{q_{l-1}}{q_{l-2}}=[a_{l-1},a_{l-2},\ldots,a_1]=\frac{{p'}_{l-2}}{{q'}_{l-2}} \]

由於漸進分數的分子分母總是互素，只能分子分母對應相等。

根據純循環，循環節的餘項與它本身相等，有：

\[ x=\frac{xp_{l-1}+p_{l-2}}{xq_{l-1}+q_{l-2}} \]

\[ q_{l-1}x^2+(q_{l-2}-p_{l-1})x-p_{l-2}=0 \]

之後只需將上述反序定理代入驗證即證完。

根據伽羅瓦連分數定理，純循環連分數的共軛一定落在 \(-1\) 到 \(0\) 之間。考慮它的逆問題，就有下面的定理：

如果二次有理數 \(x\) 大於 \(1\)，它的共軛落在 \(-1\) 到 \(0\) 之間，則它是純循環連分數。

證明

對二次無理數進行連分數算法，它的餘項 \(r_{k+1}\) 容易得到。

根據共軛落在 \(-1\) 和 \(0\) 之間，利用歸納法可以知道，餘項的共軛總是落在 \(-1\) 到 \(0\) 之間，因此部分商 \(a_k\) 是 \(r_{k+1}\) 的「倒數負共軛」的取整。這給了一種「倒推」的關係。

由拉格朗日連分數定理，x 一定是循環連分數，存在餘項 r 相同，於是它們的前一個部分商 a 相同，前一個餘項是小數部分的倒數，也相同。最後推得第 0 項在循環節中，該二次有理數純循環。

根號 d 的連分數

對於非平方整數 d，有：

\[ \sqrt{d}=[\lfloor\sqrt{d}\rfloor,\overline{a_1,a_2,\ldots,a_{l-1},2\lfloor\sqrt{d}\rfloor}] \]

\[ a_k=a_{l-k} \]

這是根號 d 的連分數形式。不僅最後一位是整數部分的兩倍，而且中間部分還是對稱的。

證明

對於非平方整數 d，二次有理數

\[ \lfloor\sqrt{d}\rfloor+\sqrt{d} \]

是純循環連分數。於是就有：

\[ \sqrt{d}=[\lfloor\sqrt{d}\rfloor,\overline{a_1,a_2,\ldots,a_{l-1},2\lfloor\sqrt{d}\rfloor}] \]

而上述純循環連分數的倒數負共軛既可以用伽羅瓦連分數定理表達，也可以由它本身直接表達：

\[ \frac{1}{-\lfloor\sqrt{d}\rfloor+\sqrt{d}}=[\overline{a_{l-1},a_{l-2},\ldots,a_1,2\lfloor\sqrt{d}\rfloor}]=[\overline{a_1,a_2,\ldots,a_{l-1},2\lfloor\sqrt{d}\rfloor}] \]

根據簡單連分數展開的唯一性就證明了該結論。

同樣也可以證明，整數部分為半整數的相同結構：

\[ \frac{\sqrt{d}}{2}=[\lfloor\frac{\sqrt{d}-1}{2}\rfloor+\frac{1}{2},\overline{a_1,a_2,\ldots,a_{l-1},2\lfloor\frac{\sqrt{d}-1}{2}\rfloor+1}] \]

\[ a_k=a_{l-k} \]

一個實例

以 \(\sqrt{74}\) 為例，實際運算一下連分數算法：

\[ \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} \]

根據伽羅瓦連分數定理，對稱的餘項 \(r_k\) 和 \(r_{l+1-k}\) 循環部分恰好相反，因此互為倒數負共軛。

如果循環節 \(l\) 是奇數，則對稱部分最中間的餘項與自己互為倒數負共軛。但如果循環節 \(l\) 是偶數，就不會出現這種現象。

在後面的 Pell 方程一節中將指出，在根號 \(d\) 的連分數中，循環節 \(l\) 的奇偶性，將直接決定 Pell 方程中的 \(-1\) 形式是否有解。

Tavrida NU Akai Contest - Continued Fraction

你得到了 \(x\) 和 \(k\),\(x\) 不是一個完全平方數。讓 \(\sqrt x = [a_0; a_1, \dots]\)，找到 \(\frac{p_k}{q_k}=[a_0; a_1, \dots, a_k]\) 的 \(0 \leq k \leq 10^9\)。

解答

在計算完 \(\sqrt x\) 的週期後，可以使用連分數表示引起的線性分數變換上的二進制冪來計算 \(a_k\)。要查找結果轉換，請將大小為 \(T\) 的週期壓縮為單個轉換，並將其重複 \(\lfloor \frac{k-1}{T}\rfloor\) 次，然後手動將其與其餘轉換組合。

Python

x, k = map(int, input().split())

mod = 10**9+7

# compose (A[0]*x + A[1]) / (A[2]*x + A[3]) and (B[0]*x + B[1]) / (B[2]*x + B[3])
def combine(A, B):
    return [t % mod for t in [A[0]*B[0]+A[1]*B[2], A[0]*B[1]+A[1]*B[3], A[2]*B[0]+A[3]*B[2], A[2]*B[1]+A[3]*B[3]]]

A = [1, 0, 0, 1] # (x + 0) / (0*x + 1) = x

a = sqrt(x)

T = len(a) - 1 # period of a

# apply ak + 1/x = (ak*x+1)/(1x+0) to (Ax + B) / (Cx + D)
for i in reversed(range(1, len(a))):
    A = combine([a[i], 1, 1, 0], A)

def bpow(A, n):
    return [1, 0, 0, 1] if not n else combine(A, bpow(A, n-1)) if n % 2 else bpow(combine(A, A), n // 2)

C = (0, 1, 0, 0) # = 1 / 0
while k % T:
    i = k % T
    C = combine([a[i], 1, 1, 0], C)
    k -= 1

C = combine(bpow(A, k // T), C)
C = combine([a[0], 1, 1, 0], C)
print(str(C[1]) + '/' + str(C[3]))

---

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用