Möbius Function and Inversion

$\mu (n)=\{\begin{array}{ll}1& n=1\\ (-1{)}^k& n\text{ is a product of }k\text{ distinct primes}\\ 0& n\text{ has a squared prime factor.}\end{array}$

$\mu$ is multiplicative, and its defining property is

${\sum }_{d\mid n}\mu (d)=[n=1].$

That indicator is what makes $\mu$ the inclusion-exclusion coefficient for divisibility.

Computing it

vector<int> mu(N + 1, 0);
mu[1] = 1;
for (int i = 1; i <= N; i++)
    for (int j = 2 * i; j <= N; j += i) mu[j] -= mu[i];      // O(N log N)

Or with a linear sieve, $O(N)$:

if (!spf[i]) { primes.push_back(i); mu[i] = -1; }
for (int p : primes) {
    if ((long long)i * p > N) break;
    if (i % p == 0) { mu[i*p] = 0; break; }                  // squared factor
    mu[i*p] = -mu[i];
}

Möbius inversion

$g(n)={\sum }_{d\mid n}f(d)⟺f(n)={\sum }_{d\mid n}\mu (d)g\left(\frac{n}{d}\right).$

There is a second, more useful form for competitive programming:

$g(n)={\sum }_{n\mid d}^{N}f(d)⟺f(n)={\sum }_{n\mid d}^N\mu \left(\frac{d}{n}\right)g(d).$

The pattern that matters

Counting pairs with $\gcd =1$:

$\#\{(i,j):i\le n,j\le m,\gcd (i,j)=1\}={\sum }_{d=1}^{\min (n,m)}\mu (d)\lfloor \frac{n}{d}\rfloor \lfloor \frac{m}{d}\rfloor .$

Derivation: $[\gcd (i,j)=1]={\sum }_{d\mid \gcd (i,j)}\mu (d)$, then swap the order of summation.

And for a general gcd value:

$\#\{\gcd (i,j)=k\}={\sum }_d\mu (d)\lfloor \frac{n}{dk}\rfloor \lfloor \frac{m}{dk}\rfloor .$

Divisor-block optimisation

$\lfloor n/d\rfloor$ takes only $O(\sqrt{n})$ distinct values. Group the sum by blocks where it is constant:

long long ans = 0;
for (long long l = 1, r; l <= n; l = r + 1) {
    r = min(n / (n / l), m / (m / l));
    ans += (prefMu[r] - prefMu[l-1]) * (n / l) * (m / l);
}

$O(\sqrt{n})$ per query after an $O(N)$ sieve of the prefix sums of $\mu$. This divisor-block (or “整除分块”) technique is essential — it turns $O(n)$ sums into $O(\sqrt{n})$ and appears in almost every Möbius problem.

Worked problems

Problem	Formula
Coprime pairs $\le n$	${\sum }_d\mu (d)\lfloor n/d{\rfloor }^2$
Pairs with $\gcd =k$	${\sum }_d\mu (d)\lfloor n/(dk){\rfloor }^2$
${\sum }_{i,j}\gcd (i,j)$	${\sum }_d\phi (d)\lfloor n/d{\rfloor }^2$ (or via $\mu$)
Squarefree numbers $\le n$	${\sum }_{d\le \sqrt{n}}\mu (d)\lfloor n/d^2\rfloor$
Count $\le n$ not divisible by any of $p_1..p_k$	inclusion-exclusion, which is $\mu$ restricted to those primes
$\sum \mathrm{lcm}(i,j)$	expand as $ij/\gcd$, then Möbius

Möbius vs plain inclusion-exclusion

They are the same principle. Explicit inclusion-exclusion over $k$ primes costs $2^k$ terms; Möbius packages exactly those $\pm 1$ signs into a single function you can sieve, so the sum runs over $d$ rather than over subsets. When the “sets” are divisibility by primes, always prefer $\mu$.

Mertens function

$M(n)={\sum }_{k\le n}\mu (k)$. Computable for huge $n$ by the same recursion used for $\Phi$:

$M(n)=1-{\sum }_{d=2}^{n}M\left(\lfloor \frac{n}{d}\rfloor \right),$

with divisor blocks and memoisation — $O(n^{2/3})$ after sieving small values. The same machinery (“Du’s sieve” / Dirichlet hyperbola method) computes prefix sums of $\phi$, $\mu$, and other multiplicative functions for $n$ up to $10^{11}$.

See also: Euler Totient · Dirichlet Convolution · Inclusion-Exclusion