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