跳转至

循环连分数

线性分式变换

连分数的另一个重要概念是所谓的线性分式变换(Linear fractional transformations)。

定义

线性分式变换 是一个函数 ,使得 对于一些

线性分式变换 的组合 也是线性分式变换:

线性分式变换的逆,也是线性分式变换:

DMOPC '19 Contest 7 P4 - Bob and Continued Fractions

给您一个正整数数组 。您需要回答 查询。每个查询都要计算

解答

如果能够连接连分数,则可以用线段树来解决这个问题。

通常情况下, 是正确的。

表示 。注意 。在这个概念中,它认为

因此,问题归结为计算

变换的组合是关联的,因此可以在线段树的每个节点中计算其子树中变换的组合。

例题 连分数的线性分式变换

。对于 ,计算 的连分数表示

从而,对任意的 ,可以计算

解答

如上所述,,因此

因此,通过依次添加 , 等,可以计算

由于 是可逆的,因此在 中也是单调的。因此,对于任何 ,都有 介于 之间。

此外,对于 ,它等于 。因此, 介于 之间。当它们相等时,它们也等于

请注意,。知道 后,可以用当前变换合成 ,并继续添加 等,寻找新的下界(floor)以达成一致,从中可以推断 等,直到恢复 的所有值。

例题 连分数算法

。计算 的连分数表示。

解答

这里的想法与前面的问题类似,但不应使用 ,而应考虑双线性分数变换

您可以将当前变换更改为 ,而不是

然后,检查 ,如果它们都一致,则在生成的分数中使用该值作为 ,并将转换更改为

循环连分数

仿照循环小数的概念,如果在连分数后面形成了循环,则形成 循环连分数

循环连分数的最小正周期一般用字母 来表示,循环的部分称为循环节。容易发现,进入循环的充要条件是余项 的重复出现。

纯循环连分数

定义

如果存在 使得 ,则连分数 被称为 纯循环(periodic)。

如果 ,其中 是纯循环,则连分数 被称为 混循环(eventually periodic)。

例如纯循环连分数:

混循环连分数:

混循环连分数后面循环的部分,最早循环的部分称为它的「纯循环部分」。

纯循环连分数的整数部分 直接进入到了循环里面,因此要求 必须至少是 1。因此,纯循环连分数大于 1。

对于 ,有 ,因此 。在循环连分数和二次方程之间存在着一般的联系。考虑以下等式:

一方面,这个方程意味着 的连分数表示是周期为

另一方面,使用渐进分数的公式,这个方程意味着

也就是说, 是其自身的线性分数变换。从等式中可以看出, 是二次方程式的根:

类似的推理代表了混循环连分数,即 代表 。事实上,从第一个方程导出 ,从第二个方程导出 ,其中 是线性分数变换。因此

可以进一步证明(由拉格朗日首先完成),对于具有整数系数的任意二次方程 ,其解 是一个混循环连分数。

拉格朗日连分数定理

关于循环连分数有一个特别重要的基础定理:

拉格朗日连分数定理:实二次有理数与循环连分数一一对应。

该定理最早由拉格朗日(Lagrange)于 1769 年证明。

根据余项的重复出现,证明循环连分数一定是二次有理数非常容易。重点在于证明二次有理数一定是循环连分数。

证明

对二次有理数执行「无限简单连分数」计算,即取倒数、取整交替,得到的余数还是二次有理数。

接下来要强行刻画余项,将余项束缚在有限的范围,有限范围里的无限余项必然会发生重复。

是如下形式的二次有理数:

如果分母不整除分子的范数,那么分子分母同时乘以分母的绝对值,并强行压入根号,在新二次有理数中,分母整除新的分子的范数。因此,任何二次有理数都能写成这形式。

根据上文的简单连分数算法:对余数取整可以得到 ,进而得到新的

取整后得到的新的 为负数,且绝对值一定比 小,因此范数为负。取倒数,得到新的分母 总是正的。

由于范数为负,取倒数之后 前面的符号不变,而 的符号由负变正(负数前面加负号变为正数)。

余数 里面,每个 都为负数,且绝对值一定比 小,因此分子 的个数有限。

每个 都整除对应 构成二次整数的范数,因此分母 的个数有限。余数有限必重复,至此证完。

例题 二次有理数

找到 的连分数,其中 不是完全平方。

解答

对于数字的第 个完全商 ,通常认为

从而,

将分子和分母乘以 ,将去掉分母中的 ,因此完全商为

接下来求解 ,假设 是已知的。

首先,。然后

因此,如果表示 ,将有

这种表示法的优点在于,如果将 减去它们的最大公约数,结果将是唯一的。因此,可以使用它来检查当前状态是否已经重复,以及检查具有此状态的上一个索引的位置。

下面是计算 的连分数表示的代码:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
# 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 互为「倒数负共轭」。即,若记:

则 x 与 y 共轭。

该定理最早由伽罗瓦(Galois)在他 17 岁那年(1828 年)发现并证明。

证明

不妨改取比较长(例如至少有 5 项)的循环节。将循环节部分反序,根据反序定理,渐进分数有:

由于渐进分数的分子分母总是互素,只能分子分母对应相等。

根据纯循环,循环节的余项与它本身相等,有:

之后只需将上述反序定理代入验证即证完。

根据伽罗瓦连分数定理,纯循环连分数的共轭一定落在 之间。考虑它的逆问题,就有下面的定理:

如果二次有理数 大于 ,它的共轭落在 之间,则它是纯循环连分数。

证明

对二次无理数进行连分数算法,它的余项 容易得到。

根据共轭落在 之间,利用归纳法可以知道,余项的共轭总是落在 之间,因此部分商 的「倒数负共轭」的取整。这给了一种「倒推」的关系。

由拉格朗日连分数定理,x 一定是循环连分数,存在余项 r 相同,于是它们的前一个部分商 a 相同,前一个余项是小数部分的倒数,也相同。最后推得第 0 项在循环节中,该二次有理数纯循环。

根号 d 的连分数

对于非平方整数 d,有:

这是根号 d 的连分数形式。不仅最后一位是整数部分的两倍,而且中间部分还是对称的。

证明

对于非平方整数 d,二次有理数

是纯循环连分数。于是就有:

而上述纯循环连分数的倒数负共轭既可以用伽罗瓦连分数定理表达,也可以由它本身直接表达:

根据简单连分数展开的唯一性就证明了该结论。

同样也可以证明,整数部分为半整数的相同结构:

一个实例

为例,实际运算一下连分数算法:

各个余项分别是:

根据伽罗瓦连分数定理,对称的余项 循环部分恰好相反,因此互为倒数负共轭。

如果循环节 是奇数,则对称部分最中间的余项与自己互为倒数负共轭。但如果循环节 是偶数,就不会出现这种现象。

在后面的 Pell 方程一节中将指出,在根号 的连分数中,循环节 的奇偶性,将直接决定 Pell 方程中的 形式是否有解。

Tavrida NU Akai Contest - Continued Fraction

你得到了 , 不是一个完全平方数。让 ,找到

解答

在计算完 的周期后,可以使用连分数表示引起的线性分数变换上的二进制幂来计算 。要查找结果转换,请将大小为 的周期压缩为单个转换,并将其重复 次,然后手动将其与其余转换组合。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
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]))