D

定义
$f(b,n) = n \;\; n < b$
$f(b,n) = f(b,n/b) + n \mod b \;\; n \geq b$

令$s = f(b,n)$
现给出$n,s$,求最小的b

数论

  • $b \leq \sqrt{n}$,直接暴力比较
  • $b > \sqrt{n}$,$n = pb + q$,$s = p + q$,$b = (n-s)/p + 1$
    我们枚举$n-s$的因子即可

复杂度$O(\sqrt{n})$

E

线段上有n个点,每天最多走L,且每天结束时必须在点上
q个询问,问最少几天从a 走到 b

倍增

预处理出每个点 $2^i$ 天可以到哪个点

复杂度$(O(n+q)logn)$