数论之莫比乌斯反演

发表于 分类于 阅读次数：

开始学习莫比乌斯反演，记录一下。

学习前的预备知识—整除分块

在求解$ \sum_{i = 1}^n\lfloor\frac{n}{i}\rfloor$ 的问题的时候，一般我们需要O（n）的遍历，但是其实有一段$\lfloor\frac{n}{i}\rfloor$是相同的，而这一个块的最后一个数字的下标就是n / (n / i),所以我们可以一块一块的算,这样就把复杂度降到了O($\sqrt{n}$)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n ;
    cin >> n;
    int ans ;
    for(int l = 1, r; l <= n; l = r+1 )
    {
        r = n / (n / l);
        ans += (r - l + 1) * (n / l);
    }
    cout << ans << '\n';
}