萌新求助一个问题
  • 板块学术版
  • 楼主m256i
  • 当前回复11
  • 已保存回复11
  • 发布时间2022/7/7 13:34
  • 上次更新2023/10/27 21:37:20
查看原帖
萌新求助一个问题
370281
m256i楼主2022/7/7 13:34

x+y=z,xyn\sqrt x+\sqrt y=\sqrt z,xy\le n 的正整数解数。

显然这个问题等价于求这个式子:

k2nd(k2)\sum_{k^2 \le n}\operatorname{d}(k^2)

其中 d\operatorname{d} 是约数个数函数。

然而我太菜了,只会写 Θ(n)\Theta(\sqrt{n}) 的暴力线性筛,能口胡出 Θ(n38logn)\Theta\left(\dfrac{n^{\frac{3}{8}}}{\log n}\right) 的 Min_25 筛做法(不会写)。想问一下,是否存在更优复杂度方法?

2022/7/7 13:34
加载中...