ACM-ICPC竞赛中的连分数理论与应用
ACM-ICPC竞赛中的连分数理论与应用
8.12.27 ACM-ICPC 数学 数论 连分数
连分数（Continued Fractions）是表示实数为有理数序列的一种特定形式。它们在算法竞赛中非常有用，因为它们易于计算，并且可以有效地找到实数的最佳有理近似。连分数与欧几里得算法密切相关，使其在数论问题中非常有用。
一、定义
连分数是一种表示实数的记法。例如，一个长度为 4 的连分数可以表示为：
[ [a_0, a_1, a_2, a_3] = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{a_3}}} ]
其中 (a_0, a_1, a_2, a_3) 是整数。连分数的各项 (a_i) 称为部分商。
二、简单连分数
简单连分数是从第 1 项开始均为正整数的连分数。如果有限，最后一项不能为 1。简单连分数具有以下性质：
- 任何有理数都可以表示为有限简单连分数。
- 无限简单连分数一定收敛。
三、无限连分数
无限连分数是指变元无限个的连分数。例如：
[ r = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cdots}} = \lim_{k \to \infty} r_k ]
其中，(r_k = [a_0; a_1, \ldots, a_k]) 称为第 (k) 个渐进分数。
四、渐进分数
渐进分数（Convergents）是连分数的部分和。例如，对于连分数 (r = [a_0; a_1, a_2, \ldots])，其第 (k) 个渐进分数 (r_k) 可以表示为：
[ r_k = \frac{p_k}{q_k} ]
其中，(p_k) 和 (q_k) 满足以下递推关系：
[ p_k = a_k p_{k-1} + p_{k-2} ]
[ q_k = a_k q_{k-1} + q_{k-2} ]
五、连分数的性质
- 递推关系：渐进分数的递推关系可以简化连分数的计算。
- 误差估计：渐进分数与实数之间的误差可以估计为 (\left| r - \frac{p_k}{q_k} \right| \leq \frac{1}{q_k q_{k+1}})。
- 反序定理：对于渐进分数，存在反序定理，用于快速计算反序。
六、连分数的应用
- 最佳有理逼近
连分数可以用于找到实数的最佳有理逼近。例如，对于实数 (r)，其渐进分数 (r_k) 是满足以下条件的最佳有理逼近：
[ \left| r - \frac{p_k}{q_k} \right| \leq \frac{1}{q_k q_{k+1}} ]
- 扩展欧几里得算法
连分数与扩展欧几里得算法密切相关，可以用于求解线性不定方程。例如，求解方程 (Ax + By = C) 时，可以利用连分数表示 (\frac{A}{B}) 的渐进分数来找到解。
- 凸包问题
连分数可以用于解决凸包问题，例如找到满足特定条件的格点的凸包。
七、例题
例题1：扩展欧几里得算法
题目：给定整数 (A)、(B) 和 (C)，求 (x) 和 (y) 使得 (Ax + By = C)。
解答：利用连分数表示 (\frac{A}{B})，找到对应的渐进分数 (r_k = \frac{p_k}{q_k})，通过扩展欧几里得算法求解。
例题2：最佳有理逼近
题目：给定一个实数 (r) 和一个整数 (n)，求使得 (\left| r - \frac{p}{q} \right|) 最小的有理数 (\frac{p}{q})，其中 (q \leq n)。
解答：利用连分数表示 (r)，找到满足条件的渐进分数 (r_k)。
八、总结
连分数作为一种强大的数论工具，具有广泛的应用。通过掌握连分数的性质和计算方法，可以解决多种复杂的数论问题，提高算法竞赛中的解题效率。