求助暴力时间复杂度
  • 板块P2257 YY的GCD
  • 楼主linxuanrui
  • 当前回复0
  • 已保存回复0
  • 发布时间2025/1/28 20:35
  • 上次更新2025/1/29 00:12:16
查看原帖
求助暴力时间复杂度
857323
linxuanrui楼主2025/1/28 20:35

一个暴力的做法。首先有答案等于 pi=1μ(i)npimpi\sum\limits_{p}\sum\limits_{i=1}^{\infty}\mu(i)\lfloor\frac{\lfloor\frac{n}{p}\rfloor}{i}\rfloor\lfloor\frac{\lfloor\frac{m}{p}\rfloor}{i}\rfloor。接下来直接对于 np\frac{n}{p} 整除分块,然后继续在内层整除分块。

貌似可以证明这个时间复杂度是 O(tn34)O(tn^{\frac{3}{4}}) 的,但是本地跑了 30s\sim30s 还是跑不完。

所以这个做法的时间复杂度到底是多少?

2025/1/28 20:35
加载中...