求 x+y=z,xy≤n\sqrt x+\sqrt y=\sqrt z,xy\le nx+y=z,xy≤n 的正整数解数。
显然这个问题等价于求这个式子:
∑k2≤nd(k2)\sum_{k^2 \le n}\operatorname{d}(k^2)∑k2≤nd(k2)
其中 d\operatorname{d}d 是约数个数函数。
然而我太菜了,只会写 Θ(n)\Theta(\sqrt{n})Θ(n) 的暴力线性筛,能口胡出 Θ(n38logn)\Theta\left(\dfrac{n^{\frac{3}{8}}}{\log n}\right)Θ(lognn83) 的 Min_25 筛做法(不会写)。想问一下,是否存在更优复杂度方法?