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

> Master Mobius inversion for competitive programming. Learn how this number theory technique transforms divisor sums into prefix sums for efficient O(sqrt N) queries. Optimize your algorithms today.

- Repository: [hzwer/shareoi](https://github.com/hzwer/shareoi)
- Tags: tutorial
- Published: 2026-03-03

---

**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:

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

```

Then Möbius inversion states that:

```text
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:

```cpp
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:

```cpp
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:

```cpp
// 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.