ACM-ICPC数学数论：连分数详解
ACM-ICPC数学数论：连分数详解
8.12.27 ACM-ICPC 数学 数论 连分数
连分数（Continued Fractions）是表示实数为有理数序列的一种特定形式。它们在算法竞赛中非常有用，因为它们易于计算，并且可以有效地找到实数的最佳有理近似。连分数与欧几里得算法密切相关，使其在数论问题中非常有用。
一、定义
连分数是一种表示实数的记法。例如，一个长度为 4 的连分数可以表示为：
[𝑎0,𝑎1,𝑎2,𝑎3]=𝑎0+1𝑎1+1𝑎2+1𝑎3[a0 ,a1 ,a2 ,a3 ]=a0 +a1 +a2 +a3 1 1 1
其中 𝑎0,𝑎1,𝑎2,𝑎3a0 ,a1 ,a2 ,a3 是整数。连分数的各项 𝑎𝑖ai 称为部分商。
二、简单连分数
简单连分数是从第 1 项开始均为正整数的连分数。如果有限，最后一项不能为 1。简单连分数具有以下性质：
- 任何有理数都可以表示为有限简单连分数。
- 无限简单连分数一定收敛。
三、无限连分数
无限连分数是指变元无限个的连分数。例如：
𝑟=𝑎0+1𝑎1+1𝑎2+⋯=lim𝑘→∞𝑟𝑘r=a0 +a1 +a2 +⋯1 1 =limk→∞ rk
其中， 𝑟𝑘=[𝑎0;𝑎1,…,𝑎𝑘]rk =[a0 ;a1 ,…,ak ] 称为第 𝑘k 个渐进分数。
四、渐进分数
渐进分数（Convergents）是连分数的部分和。例如，对于连分数 𝑟=[𝑎0;𝑎1,𝑎2,… ]r=[a0 ;a1 ,a2 ,…]，其第 𝑘k 个渐进分数 𝑟𝑘rk 可以表示为：
𝑟𝑘=𝑝𝑘𝑞𝑘rk =qk pk
其中，𝑝𝑘pk 和 𝑞𝑘qk 满足以下递推关系：
𝑝𝑘=𝑎𝑘𝑝𝑘−1+𝑝𝑘−2pk =ak pk−1 +pk−2
𝑞𝑘=𝑎𝑘𝑞𝑘−1+𝑞𝑘−2qk =ak qk−1 +qk−2
五、连分数的性质
- 递推关系：渐进分数的递推关系可以简化连分数的计算。
- 误差估计：渐进分数与实数之间的误差可以估计为 ∣𝑟−𝑝𝑘𝑞𝑘∣≤1𝑞𝑘𝑞𝑘+1∣r−qk pk ∣≤qk qk+1 1 。
- 反序定理：对于渐进分数，存在反序定理，用于快速计算反序。
六、连分数的应用
- 最佳有理逼近
连分数可以用于找到实数的最佳有理逼近。例如，对于实数 𝑟r，其渐进分数 𝑟𝑘rk 是满足以下条件的最佳有理逼近：
∣𝑟−𝑝𝑘𝑞𝑘∣≤1𝑞𝑘𝑞𝑘+1∣∣ r−qk pk ∣∣ ≤qk qk+1 1
- 扩展欧几里得算法
连分数与扩展欧几里得算法密切相关，可以用于求解线性不定方程。例如，求解方程 𝐴𝑥+𝐵𝑦=𝐶Ax+By=C 时，可以利用连分数表示 𝐴𝐵BA 的渐进分数来找到解。
- 凸包问题
连分数可以用于解决凸包问题，例如找到满足特定条件的格点的凸包。
七、例题
例题1：扩展欧几里得算法
题目：给定整数 𝐴A、𝐵B 和 𝐶C，求 𝑥x 和 𝑦y 使得 𝐴𝑥+𝐵𝑦=𝐶Ax+By=C。
解答：利用连分数表示 𝐴𝐵BA ，找到对应的渐进分数 𝑟𝑘=𝑝𝑘𝑞𝑘rk =qk pk ，通过扩展欧几里得算法求解。
例题2：最佳有理逼近
题目：给定一个实数 𝑟r 和一个整数 𝑛n，求使得 ∣𝑟−𝑝𝑞∣∣∣ r−qp ∣∣ 最小的有理数 𝑝𝑞qp ，其中 𝑞≤𝑛q≤n。
解答：利用连分数表示 𝑟r，找到满足条件的渐进分数 𝑟𝑘rk 。
八、总结
连分数作为一种强大的数论工具，具有广泛的应用。通过掌握连分数的性质和计算方法，可以解决多种复杂的数论问题，提高算法竞赛中的解题效率。