一个暴力的做法。首先有答案等于 ∑p∑i=1∞μ(i)⌊⌊np⌋i⌋⌊⌊mp⌋i⌋\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}\rfloorp∑i=1∑∞μ(i)⌊i⌊pn⌋⌋⌊i⌊pm⌋⌋。接下来直接对于 np\frac{n}{p}pn 整除分块,然后继续在内层整除分块。
貌似可以证明这个时间复杂度是 O(tn34)O(tn^{\frac{3}{4}})O(tn43) 的,但是本地跑了 ∼30s\sim30s∼30s 还是跑不完。
所以这个做法的时间复杂度到底是多少?