连分数（Continued Fractions）：用 [a0; a1, a2, …] 展开表示有理/实数，收敛分数提供“最佳有理逼近”；对有理数展开有限，复杂度 O(log max(|p|,|q|))。
Description: Continued-fraction expansion via Euclidean algorithm; convergents yield best rational approximations. Finite for rationals; periodic for quadratic irrationals. Time: O(log max(|p|,|q|)) for p/q; building convergents is linear in length Status: tested
-
函数/接口（据实现）
- contFrac(p, q) → vector
a：返回有理数 p/q (q>0) 的连分数系数 a0..ak。 - convergents(a) → vector<pair<ll,ll>>：由系数生成收敛分数 (p_i, q_i)。
- bestApprox(x, maxQ) → pair<ll,ll>：给定实数 x 和分母上界 maxQ，返回使 |x − p/q| 最小的收敛分数或其邻接“半收敛”。
- fromContFrac(a) → pair<ll,ll>：将连分数还原为最简分数 p/q。
- contFrac(p, q) → vector
-
核心算法（欧几里得 + 递推）
- 连分数展开：反复整除 p = a0·q + r，记录 a0，令 (p, q) ← (q, r) 直至 r=0。
- 收敛分数递推：
- p_{−2}=0, p_{−1}=1；q_{−2}=1, q_{−1}=0
- p_i = a_i p_{i−1} + p_{i−2}，q_i = a_i q_{i−1} + q_{i−2}
- 最佳逼近：任何分母 ≤ q_i 的分数在 |p/q − p_i/q_i| 上不优于第 i 个收敛分数；若需更细粒度可在最后一段考虑半收敛（调小最后系数）。
-
输出语义
- a：连分数系数序列（a0≥0, a_i≥1 for i≥1）。
- (p_i,q_i)：第 i 个收敛的最简分数；最后一个即原 p/q。
- bestApprox：返回 (p,q) 使 q≤maxQ 且误差近似最优。
-
复杂度
- 展开 p/q：O(log max(|p|,|q|)) 次除法；生成收敛：O(k)，k 为系数个数。
-
使用与注意
- 溢出：p_i, q_i 递推可能溢出 64 位；大数时需用 __int128/大整数。
- 实数输入：通过反复取 floor(x) 与 x ← 1/(x−floor(x)) 近似，受浮点误差影响；可设迭代/分母上限。
- 二次无理数连分数为周期，可用于 Pell 方程等问题。
- 规范化：保证 q>0，必要时整体取负统一符号。