莫比乌斯函数求法

莫比乌斯

O(n) 线性求法

不难理解，就是在欧拉线性筛的时候顺便求的。不过有个酷炫的名字，叫“O(n) 递推求解”。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int vis[N], prime[N], mu[N];
void Mobius(int n) {
    memset(vis, 0, sizeof(vis));
    mu[1] = 1;
    m = 0;
    for (int i = 2; i <= n; i++) {
        if (!vis[i]) {
            prime[++m] = i;
            mu[i] = -1;
        }
        for (int j = 1; j <= m; j++) {
            if (prime[j] * i > n) break;
            vis[i * prime[j]] = 1;
            if (i % prime[j] == 0) {
                mu[i * prime[j]] = 0;
                break;
            }
            mu[i * prime[j]] = -mu[i];
        }
    }
}

sqrt(n) 单独求解

这个基本操作

1
2
3
4
5
6
7
8
9
10
11
ll get_mu(ll n) {
    int mu = 1;
    for (int i = 2; i * i <= n; i++)
        if (n % i == 0) {
            mu = -mu;
            n /= i;
            if (n % i == 0) return 0;
        }
    if (n > 1) mu = -mu;
    return mu;
}

O(nlogn) 调和级数复杂度求法

这个有点妙！
（目前不知道原理，留坑待填）

1
2
3
4
5
6
7
int mu[N];
int main() {
    mu[1] = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = i + i; j <= n; j += i) mu[j] -= mu[i];
    }
}