Multiplicative Functions in Competitive Programming

Common form: asked to sum or count something over 1≤i≤n1 \le i \le n, or over pairs (i,j)(i, j), the quantity involves divisors, gcds, or Euler’s totient, and the obvious double loop is hopelessly slow. A surprising fraction of them collapse the moment we notice that the function in play is multiplicative.

Arithmetic and multiplicative functions

An arithmetic function is just a map f:Z+→Cf : \mathbb{Z}^{+} \to \mathbb{C} — in practice, some integer we compute from nn. It is multiplicative if f(1)=1f(1) = 1 and

f(mn)=f(m) f(n)whenever gcd⁡(m,n)=1,f(mn) = f(m)\,f(n) \qquad \text{whenever } \gcd(m, n) = 1,

and completely multiplicative if that identity holds for all m,nm, n, coprime or not. The coprimality restriction is the entire personality of the definition: it ties ff to the prime factorization and to nothing else.

Lemma. A multiplicative function is completely determined by its values on prime powers. If n=p1e1p2e2⋯pkekn = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}, then f(n)=∏i=1kf ⁣(piei)f(n) = \prod_{i=1}^{k} f\!\left(p_i^{e_i}\right).

Proof. The factors pieip_i^{e_i} are pairwise coprime, so apply the multiplicative rule k−1k - 1 times. ■\blacksquare

This is the whole reason these functions are cheap to compute: we never need to reason about a general nn, only about prime powers pep^e, and then multiply. Every algorithm below is, at heart, “do something clever at prime powers, then multiply out.”

Sources:

https://usaco.guide/adv/prefix-sums-nt-1?lang=cpp

https://usaco.guide/adv/prefix-sums-nt-2?lang=cpp

https://codeforces.com/blog/entry/53925

https://codeforces.com/blog/entry/54150

Möbius inversion

Because μ∗1=ε\mu * \mathbf{1} = \varepsilon, convolving any identity by μ\mu undoes a convolution by 1\mathbf{1}:

Möbius inversion. For arithmetic functions f,gf, g, g(n)=∑d ∣ nf(d)⟺f(n)=∑d ∣ nμ(d) g ⁣(nd).g(n) = \sum_{d \,\mid\, n} f(d) \quad\Longleftrightarrow\quad f(n) = \sum_{d \,\mid\, n} \mu(d)\, g\!\left(\tfrac{n}{d}\right).

In convolution language this is just g=f∗1  ⟺  f=g∗μg = f * \mathbf{1} \iff f = g * \mu, and the proof is one line: convolve both sides by μ\mu and use 1∗μ=ε\mathbf{1} * \mu = \varepsilon. This equivalence is the engine behind essentially every “sum over coprime pairs” trick below.

Dirichlet convolution

The reason these functions form a tidy algebra is the Dirichlet convolution:

(f∗g)(n)=∑d ∣ nf(d) g ⁣(nd).(f * g)(n) = \sum_{d \,\mid\, n} f(d)\, g\!\left(\tfrac{n}{d}\right).

Its identity element is ε\varepsilon, since in (ε∗f)(n)(\varepsilon * f)(n) only the divisor d=1d = 1 survives. The single fact that makes convolution useful in a contest is this:

Theorem. If ff and gg are multiplicative, so is f∗gf * g.

Proof. Take gcd⁡(m,n)=1\gcd(m, n) = 1. Every divisor of mnmn factors uniquely as d=abd = ab with a∣ma \mid m, b∣nb \mid n, and gcd⁡(a,b)=1\gcd(a, b) = 1. Then

(f∗g)(mn)=∑a∣m∑b∣nf(ab) g ⁣(mnab)=(∑a∣mf(a)g ⁣(ma))(∑b∣nf(b)g ⁣(nb)),(f * g)(mn) = \sum_{a \mid m} \sum_{b \mid n} f(ab)\, g\!\left(\tfrac{mn}{ab}\right) = \Big(\sum_{a \mid m} f(a) g\!\left(\tfrac{m}{a}\right)\Big)\Big(\sum_{b \mid n} f(b) g\!\left(\tfrac{n}{b}\right)\Big),

using multiplicativity of ff and gg across the coprime split abab. The right-hand side is (f∗g)(m) (f∗g)(n)(f * g)(m)\,(f * g)(n). ■\blacksquare

So multiplicative functions are closed under ∗*, and almost all the standard ones are secretly convolutions of simpler functions. The four identities to keep in memory:

1∗1=d,Id⁡∗1=σ,φ∗1=Id⁡,μ∗1=ε.\mathbf{1} * \mathbf{1} = d, \qquad \operatorname{Id} * \mathbf{1} = \sigma, \qquad \varphi * \mathbf{1} = \operatorname{Id}, \qquad \mu * \mathbf{1} = \varepsilon.

Read aloud: “the number of divisors is ∑d∣n1\sum_{d \mid n} 1”; “the sum of divisors is ∑d∣nd\sum_{d \mid n} d”; "∑d∣nφ(d)=n\sum_{d \mid n} \varphi(d) = n"; and the headline act, "∑d∣nμ(d)=[ n=1 ]\sum_{d \mid n} \mu(d) = [\,n = 1\,]". That last one says μ\mu is the Dirichlet inverse of 1\mathbf{1}.

Use case 1 — the linear sieve

Because a multiplicative ff is pinned down by its prime-power values, we can fill an array f[1…N]f[1 \ldots N] in O(N)O(N) with a linear sieve. The sieve visits every composite exactly once, through its smallest prime factor pp, so for each new number i⋅pi \cdot p we only need a rule for two cases:

  1. p∤ip \nmid i. Then gcd⁡(i,p)=1\gcd(i, p) = 1, so f(i⋅p)=f(i) f(p)f(i \cdot p) = f(i)\, f(p) — pure multiplicativity.
  2. p∣ip \mid i. Now pp is also the smallest prime of ii, and we are bumping its exponent: pk ∥ ip^k \,\|\, i becomes pk+1 ∥ i⋅pp^{k+1} \,\|\, i \cdot p. We need a rule relating f(pk+1)f(p^{k+1}) to f(pk)f(p^k), usually by tracking the relevant prime-power factor on the side.

Here is the canonical version that produces φ\varphi and μ\mu together, since they exercise both styles of recurrence:

const int N = 1000001;
int primes[N], pc = 0;
bool composite[N];
int phi[N], mu[N];

void sieve(int n) {
    phi[1] = 1; mu[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!composite[i]) { // i is prime
            primes[pc++] = i;
            phi[i] = i - 1;            // phi(p) = p - 1
            mu[i] = -1;                // mu(p)  = -1
        }
        for (int j = 0; j < pc && (long long) i * primes[j] <= n; j++) {
            int p = primes[j], ip = i * p;
            composite[ip] = true;
            if (i % p == 0) {           // case 2: p divides i
                phi[ip] = phi[i] * p;   // phi(p^{k+1}) = p * phi(p^k)
                mu[ip] = 0;             // squared prime factor => mu = 0
                break;                  // preserve the spf invariant
            } else {                    // case 1: coprime
                phi[ip] = phi[i] * (p - 1);
                mu[ip] = -mu[i];
            }
        }
    }
}

Why is it linear? The break stops at the smallest prime factor, guaranteeing each composite is struck exactly once. Drop it and this falls back to the O(Nlog⁡log⁡N)O(N \log \log N) sieve.

The same pattern computes anything multiplicative; we only swap the two recurrences. For the number of divisors d(n)d(n) we track the exponent of the smallest prime, since d(pe)=e+1d(p^e) = e + 1:

int d[N], cnt[N];   // cnt[i] = exponent of the smallest prime factor of i

void sieve_d(int n) {
    d[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!composite[i]) { primes[pc++] = i; d[i] = 2; cnt[i] = 1; }
        for (int j = 0; j < pc && (long long) i * primes[j] <= n; j++) {
            int p = primes[j], ip = i * p;
            composite[ip] = true;
            if (i % p == 0) {
                cnt[ip] = cnt[i] + 1;
                d[ip] = d[i] / (cnt[i] + 1) * (cnt[i] + 2);  // (e+1) -> (e+2)
                break;
            } else {
                cnt[ip] = 1;
                d[ip] = d[i] * 2;   // multiply by d(p) = 2
            }
        }
    }
}

Divisor sum σ\sigma works identically if we instead keep the running value 1+p+⋯+pk1 + p + \cdots + p^k for the smallest prime power. The pattern never changes: a value at primes, a step rule at prime powers, multiplicativity everywhere else.

Use case 2 — Möbius inversion and gcd sums

Here is the payoff that makes the algebra worth it. A classic task:

Problem. Given nn (say up to 10710^7), compute G(n)=∑i=1n∑j=1ngcd⁡(i,j)G(n) = \sum_{i=1}^{n} \sum_{j=1}^{n} \gcd(i, j).

The naive double loop is O(n2)O(n^2) — out of reach. But gcd⁡\gcd is built from φ\varphi through the identity φ∗1=Id⁡\varphi * \mathbf{1} = \operatorname{Id}, i.e. n=∑d∣nφ(d)n = \sum_{d \mid n} \varphi(d). Apply it to gcd⁡(i,j)\gcd(i, j):

gcd⁡(i,j)=∑d ∣ gcd⁡(i,j)φ(d)=∑d≥1φ(d) [ d∣i ] [ d∣j ].\gcd(i, j) = \sum_{d \,\mid\, \gcd(i, j)} \varphi(d) = \sum_{d \ge 1} \varphi(d)\, [\,d \mid i\,]\,[\,d \mid j\,].

Now push the sum over dd to the outside. The number of i≤ni \le n divisible by dd is ⌊n/d⌋\lfloor n/d \rfloor, and the ii and jj choices are independent, so

G(n)=∑d=1nφ(d)⌊nd⌋2.G(n) = \sum_{d=1}^{n} \varphi(d) \left\lfloor \frac{n}{d} \right\rfloor^{2}.

Sieve φ\varphi in O(n)O(n), then evaluate the sum in another O(n)O(n). Done.

// G(n) = sum_{d=1..n} phi(d) * floor(n/d)^2, assuming phi[] is already sieved.
long long gcd_sum(int n) {
    long long total = 0;
    for (int d = 1; d <= n; d++) {
        long long q = n / d;
        total += (long long) phi[d] * q * q;
    }
    return total;
}

The same move with μ\mu in place of φ\varphi counts coprime pairs: replace the condition [gcd⁡(i,j)=1][\gcd(i,j) = 1] by ∑d∣gcd⁡(i,j)μ(d)\sum_{d \mid \gcd(i,j)} \mu(d) to get

#{(i,j):gcd⁡(i,j)=1}=∑d=1nμ(d)⌊nd⌋2,\#\{(i, j) : \gcd(i, j) = 1\} = \sum_{d=1}^{n} \mu(d) \left\lfloor \frac{n}{d} \right\rfloor^{2},

which is just inclusion–exclusion over “both divisible by dd,” with μ\mu supplying the signs. Once we can spot this shape by pushing the divisor sum outward, then replace a count by a floor.

Use case 3 — sublinear prefix sums (the Du sieve)

Source: https://oi-wiki.org/math/number-theory/du/ (I still don’t really understand this one)

Question: What if nn is 101010^{10} and an O(n)O(n) array is impossible?

We often need only a prefix sum of a multiplicative function, such as Sφ(n)=∑i=1nφ(i)S_\varphi(n) = \sum_{i=1}^{n} \varphi(i) or Sμ(n)=∑i=1nμ(i)S_\mu(n) = \sum_{i=1}^{n} \mu(i). The trick (the “Du sieve”) is to convolve with 1\mathbf{1} and read the identity sideways.

Summing φ∗1=Id⁡\varphi * \mathbf{1} = \operatorname{Id} over i≤ni \le n and grouping the double sum by the quotient q=i/dq = i/d gives

n(n+1)2=∑i=1n∑d ∣ iφ(d)=∑q=1nSφ ⁣(⌊nq⌋),\frac{n(n+1)}{2} = \sum_{i=1}^{n} \sum_{d \,\mid\, i} \varphi(d) = \sum_{q=1}^{n} S_\varphi\!\left(\left\lfloor \tfrac{n}{q} \right\rfloor\right),

so, peeling off the q=1q = 1 term Sφ(n)S_\varphi(n),

Sφ(n)=n(n+1)2−∑q=2nSφ ⁣(⌊nq⌋).S_\varphi(n) = \frac{n(n+1)}{2} - \sum_{q=2}^{n} S_\varphi\!\left(\left\lfloor \tfrac{n}{q} \right\rfloor\right).

The floor ⌊n/q⌋\lfloor n/q \rfloor takes only O(n)O(\sqrt{n}) distinct values, so with divisor blocking plus memoization and a linear-sieve precompute up to about n2/3n^{2/3}, hence, the whole recursion costs O(n2/3)O(n^{2/3}). The Möbius version is even cleaner, because μ∗1=ε\mu * \mathbf{1} = \varepsilon collapses the left side to 11:

Sμ(n)=1−∑q=2nSμ ⁣(⌊nq⌋).S_\mu(n) = 1 - \sum_{q=2}^{n} S_\mu\!\left(\left\lfloor \tfrac{n}{q} \right\rfloor\right).

I will leave the implementation out since I don’t have a good one, neither I have seen it in a real problem. Top level idea involves a memoization map plus the standard block loop. The takeaway here is the pattern: convolve the target with something whose prefix sum is trivial, then recurse on the quotients.

Takeaways

What I like about multiplicative functions is how mechanical they make a subject that looks intimidating. It comes down to three reflexes:

  • Recognize that the function depends only on the prime factorization, so it is pinned down at prime powers.
  • Sieve it in O(n)O(n) when we need every value, using a prime rule and a prime-power step rule.
  • Invert with μ\mu (or convolve with φ\varphi, 1\mathbf{1}, Id⁡\operatorname{Id}) to turn a gcd or coprimality condition into a clean sum over divisors — then push that sum outward and replace counts by floors.

Almost every “sum over 1≤i,j≤n1 \le i, j \le n of some gcd thing” problem is one of these reflexes in disguise. Once we start seeing the divisor sum waiting to be pushed outside, we see it everywhere.