Multiplicative Functions

Pillar: Set — "A multiplicative function respects the prime factorization decomposition. Its value at \(n\) is determined entirely by its values at prime powers."

The Setup

You already know \(\phi(n)\) from Ch4 L5. You can sieve it in \(O(n \log \log n)\). But now a problem asks you to compute \(\phi(n)\), \(\mu(n)\), AND the number of divisors \(\tau(n)\) for every \(n\) up to \(10^7\) — all at once, in strict \(O(n)\) time, with a single pass.

The reason this is possible: all three functions share a structural property. They're all multiplicative. And multiplicative functions can be computed together using a linear sieve that processes each integer exactly once.

Take \(n = 12 = 2^2 \times 3\). If you know \(\phi(4) = 2\) and \(\phi(3) = 2\), you get \(\phi(12) = 2 \times 2 = 4\) for free. Same for \(\tau\): \(\tau(4) = 3\), \(\tau(3) = 2\), so \(\tau(12) = 3 \times 2 = 6\). The function at a composite is built from its prime power components. That's the entire game.

Definition

A function \(f : \mathbb{Z}^+ \to \mathbb{C}\) is multiplicative if:

\(f(1) = 1\), and
\(f(ab) = f(a) \cdot f(b)\) whenever \(\gcd(a, b) = 1\).

The condition \(\gcd(a, b) = 1\) is critical. Multiplicativity says nothing about \(f(ab)\) when \(a\) and \(b\) share a factor. It only works for coprime arguments.

A stronger variant: \(f\) is completely multiplicative if \(f(ab) = f(a)f(b)\) for ALL \(a, b\) — no coprimality requirement. Only a few functions have this stronger property.

Key Property: Determined by Prime Powers

Every positive integer has a unique prime factorization \(n = p_1^{a_1} p_2^{a_2} \cdots p_r^{a_r}\). The prime powers \(p_i^{a_i}\) are pairwise coprime. So if \(f\) is multiplicative:

\[f(n) = f(p_1^{a_1}) \cdot f(p_2^{a_2}) \cdots f(p_r^{a_r})\]

Once you know \(f\) at every prime power, you know \(f\) everywhere. This is the Set pillar at work — the prime factorization decomposes \(n\) into independent components, and \(f\) respects that decomposition.

Example: \(f(360) = f(2^3) \cdot f(3^2) \cdot f(5)\). Three lookups, one multiply chain.

The Catalog

Eight multiplicative functions appear constantly in competitive programming. Here they are, with their values at prime powers and a sample composite.

Symbol	Name	Definition	\(f(p^k)\)	\(f(12)\)	Completely mult?
\(\phi\)	Euler's totient	\(\\|\{a \in [1,n] : \gcd(a,n)=1\}\\|\)	\(p^{k-1}(p-1)\)	\(4\)	No
\(\mu\)	Mobius	\((-1)^r\) if squarefree (\(r\) prime factors), else \(0\)	\(-1\) if \(k=1\), \(0\) if \(k \geq 2\)	\(0\)	No
\(\tau\)	Divisor count	number of divisors of \(n\)	\(k + 1\)	\(6\)	No
\(\sigma\)	Divisor sum	sum of divisors of \(n\)	\(\frac{p^{k+1}-1}{p-1}\)	\(28\)	No
\(\text{id}\)	Identity	\(\text{id}(n) = n\)	\(p^k\)	\(12\)	Yes
\(\mathbf{1}\)	Constant one	\(\mathbf{1}(n) = 1\)	\(1\)	\(1\)	Yes
\(\varepsilon\)	Unit / Dirichlet identity	\(1\) if \(n=1\), else \(0\)	\(0\) (for \(k \geq 1\))	\(0\)	Yes*
\(\lambda\)	Liouville	\((-1)^{\Omega(n)}\) where \(\Omega\) counts prime factors with multiplicity	\((-1)^k\)	\(1\)	Yes

*\(\varepsilon\) is trivially completely multiplicative since \(\varepsilon(ab) = 0 = \varepsilon(a)\varepsilon(b)\) whenever \(a > 1\) or \(b > 1\).

Walking Through Each at \(n = 12 = 2^2 \times 3\)

\(\phi(12)\): \(\phi(4) \cdot \phi(3) = 2 \times 2 = 4\). Four integers in \([1,12]\) coprime to \(12\): \(\{1, 5, 7, 11\}\).

\(\mu(12)\): \(12 = 2^2 \times 3\). The factor \(2^2\) has exponent \(\geq 2\), so \(\mu(12) = 0\). Compare \(\mu(6) = \mu(2 \times 3) = (-1)^2 = 1\) — squarefree with two prime factors.

\(\tau(12)\): Divisors of \(12\) are \(\{1, 2, 3, 4, 6, 12\}\). Count: \(6\). From prime powers: \((2+1)(1+1) = 6\).

\(\sigma(12)\): Sum of divisors: \(1+2+3+4+6+12 = 28\). From prime powers: \(\frac{2^3-1}{2-1} \cdot \frac{3^2-1}{3-1} = 7 \times 4 = 28\).

\(\lambda(12)\): \(\Omega(12) = 3\) (two \(2\)s and one \(3\)). So \(\lambda(12) = (-1)^3 = -1\). Wait — let me recount. \(12 = 2^2 \times 3^1\), so \(\Omega(12) = 2 + 1 = 3\) and \(\lambda(12) = (-1)^3 = -1\). But the table says \(1\). Let me fix: \(\lambda(12) = \lambda(4) \cdot \lambda(3) = (-1)^2 \cdot (-1)^1 = 1 \cdot (-1) = -1\).

Correction: \(\lambda(12) = -1\). The table entry above should read \(-1\).

\(n\)	\(\phi\)	\(\mu\)	\(\tau\)	\(\sigma\)	\(\lambda\)
\(1\)	\(1\)	\(1\)	\(1\)	\(1\)	\(1\)
\(2\)	\(1\)	\(-1\)	\(2\)	\(3\)	\(-1\)
\(3\)	\(2\)	\(-1\)	\(2\)	\(4\)	\(-1\)
\(4\)	\(2\)	\(0\)	\(3\)	\(7\)	\(1\)
\(5\)	\(4\)	\(-1\)	\(2\)	\(6\)	\(-1\)
\(6\)	\(2\)	\(1\)	\(4\)	\(12\)	\(1\)
\(7\)	\(6\)	\(-1\)	\(2\)	\(8\)	\(-1\)
\(8\)	\(4\)	\(0\)	\(4\)	\(15\)	\(-1\)
\(9\)	\(6\)	\(0\)	\(3\)	\(13\)	\(1\)
\(10\)	\(4\)	\(1\)	\(4\)	\(18\)	\(1\)
\(11\)	\(10\)	\(-1\)	\(2\)	\(12\)	\(-1\)
\(12\)	\(4\)	\(0\)	\(6\)	\(28\)	\(-1\)

Spend a minute verifying a few entries. \(\mu(6) = 1\) because \(6 = 2 \times 3\) is squarefree with two prime factors. \(\tau(8) = 4\) because divisors of \(8\) are \(\{1, 2, 4, 8\}\). \(\sigma(9) = 1 + 3 + 9 = 13\).

Computing All Values via Linear Sieve in \(O(n)\)

The Eratosthenes-style sieve from Ch4 L5 computes \(\phi\) in \(O(n \log \log n)\). A linear sieve does it in \(O(n)\) — each composite is visited exactly once, through its smallest prime factor (SPF).

How the Linear Sieve Works

The linear sieve maintains a list of discovered primes. For each integer \(\texttt{current}\) from \(2\) to the limit:

If \(\texttt{current}\) has no SPF recorded, it's prime. Record its SPF as itself and add it to the primes list.
For each prime \(p\) in the list (stopping when \(p > \text{SPF}(\texttt{current})\) or the product exceeds the limit), mark \(\texttt{next} = \texttt{current} \times p\).

The key guarantee: every composite \(\texttt{next}\) is generated exactly once, as \(\texttt{next} = \texttt{current} \times p\) where \(p = \text{SPF}(\texttt{next})\).

Extending to Multiplicative Functions

When you generate \(\texttt{next} = \texttt{current} \times p\), two cases arise:

Case 1: \(p \nmid \texttt{current}\) (the easy case). Then \(\gcd(p, \texttt{current}) = 1\), so multiplicativity applies directly:

\[f(\texttt{next}) = f(p) \cdot f(\texttt{current})\]

For \(\phi\): \(\phi(\texttt{next}) = (p - 1) \cdot \phi(\texttt{current})\). For \(\mu\): \(\mu(\texttt{next}) = (-1) \cdot \mu(\texttt{current})\). For \(\tau\): \(\tau(\texttt{next}) = 2 \cdot \tau(\texttt{current})\).

Case 2: \(p \mid \texttt{current}\) (the tricky case). Now \(p\) and \(\texttt{current}\) share a factor, so you can't just multiply. You need to isolate the prime power component.

Write \(\texttt{next} = p^a \times m\) where \(\gcd(p, m) = 1\). The value \(p^a\) is the full power of \(p\) in \(\texttt{next}\). The cofactor \(m = \texttt{next} / p^a\) is coprime to \(p\). Then:

\[f(\texttt{next}) = f(p^a) \cdot f(m)\]

To make this work in \(O(1)\) per composite, track one extra array: \(\texttt{highestSPFPower}[n]\) stores the largest power of \(\text{SPF}(n)\) that divides \(n\). When \(p \mid \texttt{current}\):

\(\texttt{highestSPFPower}[\texttt{next}] = \texttt{highestSPFPower}[\texttt{current}] \times p\)
\(\text{cofactor} = \texttt{next} / \texttt{highestSPFPower}[\texttt{next}]\)
\(f(\texttt{next}) = f(\texttt{highestSPFPower}[\texttt{next}]) \cdot f(\text{cofactor})\)

The cofactor's value is already computed (it's smaller than \(\texttt{next}\)), and \(f(p^a)\) at prime powers is cheap — you either precompute it or derive it from the exponent \(a\).

Trace for \(n = 12\)

Processing composites in order of generation:

\(\texttt{next}\)	\(\texttt{current} \times p\)	Case	Computation
\(4\)	\(2 \times 2\)	\(p \mid \texttt{current}\)	\(\text{SPFPower} = 4\), cofactor \(= 1\). \(\phi(4) = \phi(4) \cdot \phi(1) = 2\). \(\mu(4) = 0\). \(\tau(4) = 3\).
\(6\)	\(3 \times 2\)	\(p \nmid \texttt{current}\)	\(\phi(6) = 1 \cdot 2 = 2\). \(\mu(6) = (-1)(-1) = 1\). \(\tau(6) = 2 \cdot 2 = 4\).
\(8\)	\(4 \times 2\)	\(p \mid \texttt{current}\)	\(\text{SPFPower} = 8\), cofactor \(= 1\). \(\phi(8) = 4\). \(\mu(8) = 0\). \(\tau(8) = 4\).
\(9\)	\(3 \times 3\)	\(p \mid \texttt{current}\)	\(\text{SPFPower} = 9\), cofactor \(= 1\). \(\phi(9) = 6\). \(\mu(9) = 0\). \(\tau(9) = 3\).
\(10\)	\(5 \times 2\)	\(p \nmid \texttt{current}\)	\(\phi(10) = 1 \cdot 4 = 4\). \(\mu(10) = (-1)(-1) = 1\). \(\tau(10) = 2 \cdot 2 = 4\).
\(12\)	\(6 \times 2\)	\(p \mid \texttt{current}\)	\(\text{SPFPower} = 4\), cofactor \(= 3\). \(\phi(12) = 2 \cdot 2 = 4\). \(\mu(12) = 0\). \(\tau(12) = 3 \cdot 2 = 6\).

Every composite touched exactly once. Total work: \(O(n)\).

The Code

#include <bits/stdc++.h>
using namespace std;

void linearSieveMultiplicative(int limit) {
    vector<int> smallestPrimeFactor(limit + 1, 0);
    vector<int> highestSPFPower(limit + 1, 0);
    vector<long long> phi(limit + 1, 0);
    vector<int> mu(limit + 1, 0);
    vector<int> tau(limit + 1, 0);
    vector<int> primes;

    phi[1] = 1;
    mu[1] = 1;
    tau[1] = 1;

    for (int current = 2; current <= limit; current++) {
        if (smallestPrimeFactor[current] == 0) {
            smallestPrimeFactor[current] = current;
            highestSPFPower[current] = current;
            phi[current] = current - 1;
            mu[current] = -1;
            tau[current] = 2;
            primes.push_back(current);
        }

        for (int j = 0; j < (int)primes.size()
                && primes[j] <= smallestPrimeFactor[current]
                && (long long)current * primes[j] <= limit; j++) {

            int next = current * primes[j];
            smallestPrimeFactor[next] = primes[j];

            if (primes[j] == smallestPrimeFactor[current]) {
                highestSPFPower[next] = highestSPFPower[current] * primes[j];
                int primePower = highestSPFPower[next];
                int cofactor = next / primePower;

                int exponent = 0;
                int temp = primePower;
                while (temp > 1) { temp /= primes[j]; exponent++; }

                phi[next] = phi[cofactor] * (primePower - primePower / primes[j]);
                mu[next] = 0;
                tau[next] = tau[cofactor] * (exponent + 1);
            } else {
                highestSPFPower[next] = primes[j];
                phi[next] = phi[current] * (primes[j] - 1);
                mu[next] = -mu[current];
                tau[next] = tau[current] * 2;
            }
        }
    }
}

\(O(n)\) time, \(O(n)\) space.

Why \(\mu(\texttt{next}) = 0\) When \(p \mid \texttt{current}\)

If \(p\) already divides \(\texttt{current}\), then \(p^2\) divides \(\texttt{next}\). A number divisible by a perfect square has \(\mu = 0\) — always. No need to check the cofactor.

Why the Exponent Loop Doesn't Break \(O(n)\)

The while (temp > 1) loop computes the exponent \(a\) from the prime power \(p^a\). This looks like extra work, but the exponent is at most \(\log_2 n\), and this loop only runs when \(p \mid \texttt{current}\) — which happens at most once per composite (since we stop at \(p \leq \text{SPF}\)). The total extra work across all \(n\) is \(O(n)\).

If you want to avoid even this, store the exponent in a separate array and increment it in Case 2. The code above keeps it simple.

Complexity

\(O(n)\) time, \(O(n)\) space — each integer from \(2\) to \(n\) is processed exactly once as a composite (or identified as prime).

Common Mistakes

Forgetting \(f(1) = 1\). Every multiplicative function satisfies \(f(1) = 1\). If you skip initializing the base cases for \(n = 1\), the sieve produces garbage for every number whose cofactor is \(1\) (all prime powers).
Applying multiplicativity when \(\gcd \neq 1\). The formula \(f(ab) = f(a)f(b)\) only works when \(a\) and \(b\) are coprime. In Case 2 of the sieve, you CANNOT write \(\phi(\texttt{next}) = \phi(p) \cdot \phi(\texttt{current})\) because \(p\) and \(\texttt{current}\) share the factor \(p\). You must isolate the full prime power and multiply by the coprime cofactor.
Confusing \(\tau(p^k) = k + 1\) with \(\tau(p^k) = k\). The divisors of \(p^k\) are \(\{1, p, p^2, \ldots, p^k\}\) — that's \(k + 1\) of them, not \(k\). Off-by-one here corrupts every composite whose factorization contains that prime.

Quick Recap

A multiplicative function satisfies \(f(1) = 1\) and \(f(ab) = f(a)f(b)\) when \(\gcd(a,b) = 1\).
Multiplicativity means \(f\) is fully determined by its values at prime powers \(p^k\).
The eight standard functions (\(\phi, \mu, \tau, \sigma, \text{id}, \mathbf{1}, \varepsilon, \lambda\)) cover nearly every divisor-sum problem in competitive programming.
A linear sieve computes ANY multiplicative function over \([1, n]\) in \(O(n)\) by tracking the highest SPF power and splitting into coprime/non-coprime cases.
Multiple multiplicative functions can be computed simultaneously in a single sieve pass.

Problems

Problem	Link	Difficulty	Focus
CSES — Euler's Totient	cses.fi/problemset/task/2417	Medium	Sieve all \(\phi\) values; sum \(\phi(1) + \cdots + \phi(n)\)
CF 1139D — Steps to One	codeforces.com/problemset/problem/1139/D	Hard	Mobius function + expected value; requires knowing \(\mu\) values
CF 236B — Easy Number Challenge	codeforces.com/problemset/problem/236/B	Easy	Sieve \(\tau\) for all values; direct application

Next up: Dirichlet convolution gives you a way to COMPOSE multiplicative functions — turning the divisor sum identity \(\sum_{d \mid n} \phi(d) = n\) from a curiosity into a tool.