https://www.luogu.com.cn/article/r8ecgdam

复杂度为 $O(n^{\frac{3}{4}}\log \sqrt{n})$，虽然不是最优解但个人认为思路更简单的做法。