循环连分数

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

通常情况下， 是正确的。

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

因此，问题归结为计算

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

如上所述，，因此 。

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

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

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

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

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

您可以将当前变换更改为 或 ，而不是 。

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

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

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

设 是如下形式的二次有理数：

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

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

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

由于范数为负，取倒数之后 前面的符号不变，而 的符号由负变正（负数前面加负号变为正数）。

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

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

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

从而，

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

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

首先，。然后

因此，如果表示 ，将有

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

下面是计算 的连分数表示的代码： === "Python"

```py
# 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”函数，但不同的初始 , 和 ，可以计算任意 。

不妨改取比较长（例如至少有 5 项）的循环节。将循环节部分反序，根据反序定理，渐进分数有：

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

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

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

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

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

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

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

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

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

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

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

```py
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]))
```