开始学习莫比乌斯反演,记录一下。
学习前的预备知识—整除分块
在求解$ \sum_{i = 1}^n\lfloor\frac{n}{i}\rfloor$ 的问题的时候,一般我们需要O(n)的遍历,但是其实有一段$\lfloor\frac{n}{i}\rfloor$是相同的,而这一个块的最后一个数字的下标就是n / (n / i),所以我们可以一块一块的算,这样就把复杂度降到了O($\sqrt{n}$)。
1 |
|
云腾致雨,露结为霜
开始学习莫比乌斯反演,记录一下。
在求解$ \sum_{i = 1}^n\lfloor\frac{n}{i}\rfloor$ 的问题的时候,一般我们需要O(n)的遍历,但是其实有一段$\lfloor\frac{n}{i}\rfloor$是相同的,而这一个块的最后一个数字的下标就是n / (n / i),所以我们可以一块一块的算,这样就把复杂度降到了O($\sqrt{n}$)。
1 | #include <bits/stdc++.h> |