萌新求助素数整除分块
  • 板块学术版
  • 楼主渐变色
  • 当前回复2
  • 已保存回复2
  • 发布时间2022/4/2 22:19
  • 上次更新2023/10/28 04:49:06
查看原帖
萌新求助素数整除分块
224584
渐变色楼主2022/4/2 22:19

萌新遇到这样一个整除分块,如以下伪代码,r=mpπ(ml)r=\left\lfloor\dfrac{m}{p_{\pi(\frac{m}{l})}}\right\rfloor,请问它的时间复杂度是多少?这里蒟蒻得到一个下界为O(mlogm)O(\sqrt{\frac{m}{logm}}),经测试实际增长速率比这慢,不知道是否可以达到O(mlogm)O(\frac{\sqrt{m}}{logm})?望大佬解答qwq

i64 n;
sieve(sqrt(n));
//What is the time complexity of the following code?
i64 m = pow(n, 0.7); // pow(n, 2/3) <= m <= pow(n, 3/4)
int _v = sqrt(m);
for (int l = m / sqrt(n) + 1, r; l <= _v; l = r + 1) r = m / primes[pi[m / l]];
2022/4/2 22:19
加载中...