求问一个暴力的复杂度
  • 板块学术版
  • 楼主Jeefy
  • 当前回复16
  • 已保存回复16
  • 发布时间2023/11/20 20:23
  • 上次更新2023/11/20 22:08:09
查看原帖
求问一个暴力的复杂度
747541
Jeefy楼主2023/11/20 20:23

如果我直接计算下式的复杂度是什么,如何证明?

∑d∣mφ(d)\sum_{d | m} \varphi(d)

我指的是 O(m)O(\sqrt m) 的枚举因数,然后 O(d)O(\sqrt d) 的计算 φ(d)\varphi(d)

我知道它 =m= m

2023/11/20 20:23
加载中...