定义正整数n的舍入平方根为与$\sqrt{n}$最接近的整数。

以下过程（实际上就是增加了舍入运算的Heron法）能够用于计算n的舍入平方根：

设n共d位。若d是奇数，就取初值$x_0=2\times 10^{(d-1)⁄2}$，否则取初值$x_0=7\times 10^{(d-2)⁄2}$，之后不断迭代计算 $$x_{k+1}=\left\lfloor{\dfrac{x_k +\lceil{n / x_k}\rceil}{2}}\right\rfloor,$$ 直到$x_{k+1}=x_k$为止。例如，用上述方法计算$n=4321$的舍入平方根，初值为$x_0=7\times 10^{(4-2)⁄2}=70$，接下来有 \begin{align*} x_1&=\left\lfloor\frac{70 + \left\lceil\frac{4321}{70}\right\rceil}{2}\right\rfloor = 66 \\ x_2&=\left\lfloor\frac{66 + \left\lceil\frac{4321}{66}\right\rceil}{2}\right\rfloor = 66 \end{align*} 此时$x_2=x_1$，因此迭代终止。即经过两次迭代，就得到了4321的舍入平方根为66（$\sqrt{4321}\approx65.7343137\ldots$）。

该方法收敛速度很快，例如，对于所有的五位数，平均只需3.2102888889次迭代就能求出舍入平方根。

对所有的14位数，平均需要多少次迭代能求出舍入平方根？将答案四舍五入到10位小数。

本题难度:

解答

题面中提及的Heron法就是牛顿法解$x^2-n=0$时的特例，对这一方程而言牛顿法只要初值足够近，牛顿法就具有平方收敛性，因此只需很少的迭代次数就能得到足够近似的结果。

实现时使用深度优先搜索推进迭代的步数和范围，每一步迭代都遍历所有n，注意到$\lceil n/x\rceil$的值对x到$\lceil n/x\rceil x$之间的n都相同，因此在每一步的迭代中咋遍历n时可以不断以x为步长。

最终结果是$4.4474011180$。

注：牛顿法一般在我国《高等数学》、《数学分析》提及、其收敛性一般在《数值分析》等课程中讲授。

注2：计算量较大，以下代码中打印了进度信息。此外，代码为Python 3，因需要使用浮点除法以及需要math.ceil的返回值为整型。

import math

count=0

q=[(1,7000000,10**13,10**14-1)]
i=0
while q:
    k,x,a,b=q.pop()
    n=a
    while n<=b:
        t=math.ceil(n/x)
        m=min(b,t*x)
        y=(t+x)//2
        if y==x:
            count+=(m-n+1)*k
        else:
            q.append((k+1,y,n,m))
        n=m+1
    i+=1
    if i%1000000==0:print(i//1000000,"million popped")

print("%.10f" %(count/(10**14-10**13)))