QOJ.ac

QOJ

Type: Editorial

Status: Open

Posted by: jiangly

Posted at: 2026-04-15 16:05:33

Last updated: 2026-04-15 16:05:36

Back to Problem

题解

我们知道串联电阻是求和,并联电阻是调和平均数。那么串联 $1\Omega$ 电阻相当于分子加上分母,并联 $1\Omega$ 电阻相当于分母加上分子,于是我们可以对 $\sqrt D$ 进行连分数近似。根据连分数理论,连分数的任何截断 $\frac{p_n}{q_n}$ 的误差不超过 $\frac{1}{q_n^2}$,因为这是分母不超过 $q_n$ 时的最佳近似。可以验证在本题的数据范围内误差总是不超过 $10^{-6}$。事实上,可以证明渐进意义下假设边数是 $M$,则误差不会超过 $D^{-\Theta\left(\frac{M}{\sqrt D}\right)}$。

Comments

No comments yet.