Chapter 129

Möbius Function and Inclusion

μ(n) = 0 if n has a squared prime factor, (−1)^k if n is product of k distinct primes. Used in Möbius inversion: given F(n) = Σ f(d) for d|n, recover f(n) = Σ μ(d) × F(n/d).

Möbius Sieve

C++ — Möbius function up to N

vector mobius_sieve(int n) {
    vector mu(n + 1, 1), primes;
    vector is_composite(n + 1, false);

    for (int i = 2; i <= n; i++) {
        if (!is_composite[i]) {
            primes.push_back(i);
            mu[i] = -1;
        }
        for (int p : primes) {
            if (i * p > n) break;
            is_composite[i * p] = true;
            if (i % p == 0) { mu[i * p] = 0; break; }
            mu[i * p] = -mu[i];
        }
    }
    return mu;
}

// O(N). μ(n) is 0, 1, or -1.