Applying Möbius Inversion in Number Theory Problems for Competitive Programming: A Complete Guide

Möbius inversion transforms divisor-sum problems into computable prefix sums by exploiting the multiplicative properties of the Möbius function μ(n), enabling O(√N) query solutions after O(N) preprocessing.

The shareOI repository maintains a comprehensive collection of lecture materials for Chinese Olympiad in Informatics (OI) training, including detailed slide decks and reference PDFs that cover advanced number theory techniques. This guide synthesizes the theoretical foundations found in 数学/莫比乌斯反演_王天懿.ppt and 数学/莫比乌斯反演_方泓杰.pdf with a production-ready C++ implementation for applying Möbius inversion in competitive programming contests.

What Is Möbius Inversion?

Möbius inversion is a technique in multiplicative number theory that recovers an arithmetic function from its divisor sum. In competitive programming, it is essential for solving problems that ask for sums over greatest common divisors (GCD) or least common multiples (LCM), where direct enumeration of divisors is too slow.

The Core Inversion Formula

If two arithmetic functions f and g satisfy the relationship:

g(n) = Σ_{d|n} f(d)

Then Möbius inversion states that:

f(n) = Σ_{d|n} μ(d) · g(n/d)

Where μ(n) (the Möbius function) is defined as:

• μ(1) = 1
• μ(n) = 0 if n has a squared prime factor
• μ(n) = (-1)^k if n is the product of k distinct primes

Locating the Theory in shareOI

The shareOI repository organizes its mathematical content under the 数学/ directory. For Möbius inversion specifically, the following files provide the theoretical background and worked examples:

File	Path	Format	Content Summary
Möbius Inversion (Slides)	数学/莫比乌斯反演_王天懿.ppt	PowerPoint	Introduces μ(n), properties of multiplicative functions, and the inversion theorem with proof sketches.
Möbius Inversion (PDF)	数学/莫比乌斯反演_方泓杰.pdf	PDF	Condensed reference version optimized for quick lookup during contests.
Number Theory Fundamentals	数学/数论_杨定澄.pdf	PDF	Covers prerequisites including the totient function, divisors, and Dirichlet convolution.
Linear Sieve & Multiplicative Functions	数学/线性筛法与积性函数_贾志鹏.pptx	PowerPoint	Essential for understanding how to compute μ(n) in O(N) time using a linear sieve.

Implementing Möbius Inversion in C++

The following implementation demonstrates the complete workflow taught in the shareOI materials: computing the Möbius function via linear sieve, building prefix sums, and answering queries using the block decomposition technique (also known as the "division into blocks" or "sqrt trick").

Linear Sieve for the Möbius Function

The linear sieve computes μ(n) for all n ≤ LIMIT in O(LIMIT) time by marking composite numbers and tracking the parity of distinct prime factors:

constexpr int LIMIT = 1'000'000;
vector<int> mu(LIMIT + 1), primes;
vector<bool> isComp(LIMIT + 1);

void mobius_sieve() {
    mu[1] = 1;
    for (int i = 2; i <= LIMIT; ++i) {
        if (!isComp[i]) {
            primes.push_back(i);
            mu[i] = -1;                 // μ(p) = -1 for prime p
        }
        for (int p : primes) {
            long long v = 1LL * i * p;
            if (v > LIMIT) break;
            isComp[v] = true;
            if (i % p == 0) {           // p^2 divides v
                mu[v] = 0;              // square factor ⇒ μ = 0
                break;
            } else {
                mu[v] = -mu[i];         // μ(i·p) = -μ(i)
            }
        }
    }
}

Prefix Sum Optimization

To answer range queries of the form Σ_{d=l}^{r} μ(d) in O(1), build a prefix sum array:

long long prefixMu[LIMIT + 1];

void build_prefix() {
    prefixMu[0] = 0;
    for (int i = 1; i <= LIMIT; ++i) {
        prefixMu[i] = prefixMu[i - 1] + mu[i];
    }
}

Block Decomposition for Divisor Queries

The key optimization for competitive programming applies when computing sums over divisors. Since ⌊n/d⌋ changes only O(√n) times, we iterate over intervals [l, r] where the quotient is constant:

// Compute Σ_{d=1}^{n} μ(d) * (n/d) * (n/d + 1) / 2
// This corresponds to Σ_{d|n} d via Möbius inversion
long long sumDivisors(long long n) {
    long long ans = 0;
    for (long long l = 1, r; l <= n; l = r + 1) {
        long long q = n / l;               // floor(n / d) is constant in [l, r]
        r = n / q;
        long long muSum = prefixMu[r] - prefixMu[l - 1];
        ans += muSum * (q * (q + 1) / 2);
    }
    return ans;
}

Practical Workflow for Contest Problems

When encountering a problem that asks for a sum over GCDs, coprime pairs, or divisor functions, follow this workflow derived from the shareOI training materials:

1. Identify the Dirichlet convolution: Express the given function g(n) as a divisor sum of a simpler function f(d), i.e., g = f * 1 (where 1 is the constant function).
2. Apply Möbius inversion: Recover f using f = g * μ, converting the problem into computing prefix sums of the Möbius function.
3. Optimize queries: Use the linear sieve to pre-compute μ(n) up to the maximum constraint (typically 10^6 to 10^7), build prefix sums, and answer each query in O(√N) using block decomposition.

Summary

• Möbius inversion reverses divisor-sum relationships via the formula f(n) = Σ_{d|n} μ(d)·g(n/d), enabling efficient computation of arithmetic functions.
• The shareOI repository provides authoritative learning materials in 数学/莫比乌斯反演_王天懿.ppt and 数学/莫比乌斯反演_方泓杰.pdf that cover the theory and contest applications.
• A linear sieve computes μ(n) in O(N) time, while prefix sums and block decomposition allow O(√N) query processing—essential for solving problems involving GCD sums, coprime counting, and divisor functions under tight time limits.

Frequently Asked Questions

How does Möbius inversion differ from inclusion-exclusion?

While inclusion-exclusion is a general combinatorial principle for counting unions of sets, Möbius inversion is a specific technique for Dirichlet convolutions over divisors. In practice, Möbius inversion provides a direct algebraic formula to invert g(n) = Σ_{d|n} f(d) without manually iterating over subsets, making it more efficient for large n in competitive programming.

What is the time complexity of the linear sieve for Möbius function computation?

The linear sieve computes the Möbius function for all integers up to N in O(N) time and O(N) space. This is optimal because each composite number is marked exactly once by its smallest prime factor, and every prime is visited only during the sieving process. For typical contest constraints (N ≤ 10^7), this preprocessing is fast enough to fit within the 1-2 second time limit.

When should I use block decomposition with Möbius inversion?

Use block decomposition (also called the "sqrt trick") when you need to compute sums of the form Σ_{d=1}^{n} μ(d) · f(⌊n/d⌋) for multiple queries. Since the value of ⌊n/d⌋ changes only O(√n) times, grouping consecutive d with identical quotients reduces the per-query complexity from O(n) to O(√n). This is crucial for problems with n up to 10^9 or 10^12 where linear iteration is impossible.

Can Möbius inversion handle multiplicative functions other than the constant function?

Yes, Möbius inversion applies to any Dirichlet convolution of the form g = f * h, where h is an arithmetic function with a Dirichlet inverse. The standard case uses h = 1 (the constant function), but the theory extends to other multiplicative functions like the Euler totient φ or the divisor function σ. In competitive programming, however, the g(n) = Σ_{d|n} f(d) form is most common because it directly relates to counting problems involving GCD and LCM.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}