Mobius Function
Use the Mobius function and inversion to separate exact divisibility structure from overcounted multiples.
Mobius Function
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
The Mobius function \(\mu(n)\) is the standard tool for removing overcounting across divisors. In practice it appears when a problem wants ``gcd equals \(1\)'' or ``exactly this divisor'' and the easier count is over multiples instead.
When to Use It
Use it when:
divisor inclusion-exclusion is visible,
you can count objects divisible by \(d\) more easily than objects with gcd exactly \(1\),
a multiplicative-function sieve is already nearby.
Core Idea
The Mobius function is:
\(0\) if \(n\) has a squared prime factor,
\(1\) if \(n\) is a product of an even number of distinct primes,
\(-1\) if \(n\) is a product of an odd number of distinct primes.
Its main identity is \[ \sum_{d \mid n} \mu(d) =
\]
Key Insight
That identity is a switch that isolates gcd \(=1\). When you sum over divisors with coefficient \(\mu(d)\), every number with a larger common divisor cancels out.
Worked Problem
Problem.
How many pairs \((x, y)\) with \(1 \le x \le n\), \(1 \le y \le m\) satisfy \(\gcd(x, y) = 1\)?
Why Mobius fits.
For one divisor \(d\), the number of pairs where \(d\) divides both numbers is \[ \left\lfloor \frac{n}{d} \right\rfloor \left\lfloor \frac{m}{d} \right\rfloor. \] Applying Mobius inversion gives \[ \sum_{d=1}^{\min(n,m)} \mu(d)\left\lfloor \frac{n}{d} \right\rfloor \left\lfloor \frac{m}{d} \right\rfloor. \]
Correctness Intuition
Each pair contributes to all common divisors of \(\gcd(x,y)\). The Mobius coefficients cancel every pair whose gcd is greater than \(1\), leaving only the coprime pairs.
Complexity Analysis
Computing \(\mu\) up to \(N\) by linear sieve takes \(O(N)\). The direct summation formula above is \(O(N)\), with further harmonic-speed tricks possible in heavier problems.
Implementation
The code computes \(\mu\) with a linear sieve and includes the coprime-pair formula.
Common Pitfalls
Mixing Mobius inversion with Euler phi; they answer different questions.
Forgetting that squareful numbers contribute \(0\).
Expanding divisor sums naively without checking whether a harmonic grouping is needed.
Variants / Extensions
Mobius inversion on Dirichlet convolution.
Counting tuples with gcd \(1\).
Summatory multiplicative-function problems with prefix tricks.
Practice Problems
Count coprime pairs.
Count pairs with gcd exactly \(g\).
Any divisor-sum problem where cancellation over multiples is the main obstacle.
References
Code
Contest-ready reference implementation for the idea explained above.
struct MobiusSieve {
vector<int> primes;
vector<int> mu;
vector<bool> is_composite;
explicit MobiusSieve(int n) : mu(n + 1, 0), is_composite(n + 1, false) {
mu[1] = 1;
for (int i = 2; i <= n; ++i) {
if (!is_composite[i]) {
primes.push_back(i);
mu[i] = -1;
}
for (int p : primes) {
if (1LL * i * p > n) break;
is_composite[i * p] = true;
if (i % p == 0) {
mu[i * p] = 0;
break;
}
mu[i * p] = -mu[i];
}
}
}
};
long long count_coprime_pairs(int n, int m) {
int limit = min(n, m);
MobiusSieve sieve(limit);
long long answer = 0;
for (int d = 1; d <= limit; ++d) {
answer += 1LL * sieve.mu[d] * (n / d) * (m / d);
}
return answer;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.