AIOJ

This article introduces Dirichlet convolution and Dirichlet generating functions.

Dirichlet convolution

For arithmetic functions $f(n)$ and $g(n)$ , their Dirichlet convolution (Dirichlet convolution), denoted by $f \ast g$ , is the arithmetic function

(f \ast g)(n) = \sum_{k\mid n}f(k)g\left(\dfrac{n}{k}\right) = \sum_{k\ell=n}f(k)g(\ell).

Dirichlet convolution is an important operation on arithmetic functions. Many properties of arithmetic functions can be uncovered through this operation.

Examples

The identity function $\varepsilon$ is the Dirichlet convolution of the Möbius function $\mu$ and the constant function $1$ :
$\varepsilon=\mu \ast 1 \iff\varepsilon(n)=\sum_{d\mid n}\mu(d).$
The divisor-counting function $\tau$ is the Dirichlet convolution of the constant function $1$ with itself:
$\tau=1 \ast 1 \iff \tau(n)=\sum_{d\mid n}1.$
The divisor-sum function $\sigma$ is the Dirichlet convolution of the identity function $\mathrm{id}$ and the constant function $1$ :
$\sigma=\mathrm{id} \ast 1 \iff\sigma(n)=\sum_{d\mid n}d.$
Euler's totient function $\varphi$ is the Dirichlet convolution of the identity function $\mathrm{id}$ and the Möbius function $\mu$ :
$\varphi=\mathrm{id}\ast \mu \iff\varphi(n)=\sum_{d\mid n}d\cdot\mu\left(\frac{n}{d}\right).$

Möbius inversion uses $\varepsilon=\mu \ast 1$ to transform identities of arithmetic functions.

Properties

Dirichlet convolution has a series of algebraic properties.

Theorem

Let $f,g,h$ be arithmetic functions. Then:

Commutativity: $f\ast g=g\ast f$ .
Associativity: $(f\ast g)\ast h=f\ast(g\ast h)$ .
Distributivity: $(f+g)\ast h = f\ast h + g\ast h$ .
Identity element: $f\ast\varepsilon = \varepsilon \ast f = f$ , where $\varepsilon(n) = [n=1]$ is the identity element for convolution, and $[\cdot]$ is the Iverson bracket.
Inverse: If and only if $f(1)\neq 0$ , there exists $g$ such that $f\ast g=g\ast f=\varepsilon$ . The function $g$ is called the Dirichlet inverse of $f$ and can be denoted by $f^{-1}$ . Moreover, the inverse $g$ satisfies the recurrence
$g(n) = \dfrac{\varepsilon(n) - \sum_{k\ell = n,~k\neq 1}f(k)g(\ell)}{f(1)}.$

Proof

To verify commutativity, direct computation gives

(f\ast g)(n) = \sum_{k\ell=n}f(k)g(\ell) = (g\ast f)(n).

To verify associativity, direct computation gives

((f\ast g)\ast h)(n) = \sum_{k\ell m = n}f(k)g(\ell)h(m) = (f\ast (g\ast h))(n).

To verify distributivity, direct computation gives

\begin{aligned} ((f+g)\ast h)(n) &= \sum_{k\ell = n}(f(k) + g(k))h(\ell) \\ &= \sum_{k\ell=n}f(k)h(\ell) + \sum_{k\ell=n}g(k)h(\ell) = (f\ast h+g\ast h)(n). \end{aligned}

To verify that $\varepsilon(n)$ is the identity element, direct computation gives

(f\ast\varepsilon)(n) = \sum_{k\ell = n}f(k)\varepsilon(\ell) = f(n).

The second equality holds because $\varepsilon(\ell)$ is nonzero only when $\ell=1$ , that is, when $k=n$ .

Finally, we need to prove that $f^{-1}$ exists if and only if $f(1)\neq 0$ . For any $f$ , suppose that there is a $g$ such that $f\ast g=\varepsilon$ . This means that

(f\ast g)(n) = \sum_{k\ell = n}f(k)g(\ell) = \varepsilon(n).

This gives a system of equations for the values $g(n)$ , from which $g(n)$ can be determined directly. In particular, when $n=1$ , the equation becomes $f(1)g(1)=1$ , so the existence of $g$ requires at least $f(1)\neq 0$ . Conversely, whenever $f(1)\neq 0$ , we can solve directly for

g(n) = \dfrac{\varepsilon(n) - \sum_{k\ell = n,~k\neq 1}f(k)g(\ell)}{f(1)}.

This can be used to compute the values of $g(n)$ recursively. Therefore, the inverse $g$ exists if and only if $f(1)\neq 0$ .

In the language of abstract algebra, these algebraic properties mean that all arithmetic functions form a commutative ring under pointwise addition and Dirichlet convolution, and its units are precisely the functions that are nonzero at $n=1$ . This ring is called the Dirichlet ring (Dirichlet ring).

Multiplicative functions are a special class of arithmetic functions. They are closed under Dirichlet convolution and Dirichlet inversion.

Theorem

Let $f,g$ be multiplicative functions. Then $f\ast g$ is also multiplicative. Moreover, the inverse $f^{-1}$ always exists and is also multiplicative.

Proof

For the first claim, let $h=f\ast g$ . Direct verification shows that, for $n_1\perp n_2$ ,

\begin{aligned} h(n_1)h(n_2) &= \left(\sum_{k_1\ell_1=n_1}f(k_1)g(\ell_1)\right)\left(\sum_{k_2\ell_2=n_2}f(k_2)g(\ell_2)\right)\\ &= \sum_{k_1\ell_1=n_1,~k_2\ell_2=n_2}f(k_1)f(k_2)g(\ell_1)g(\ell_2)\\ &= \sum_{k\ell = n_1n_2}f(k)g(\ell) \\ &= h(n_1n_2). \end{aligned}

The logic behind changing the order of summation in the third equality is as follows: when $k$ ranges over the divisors of $n_1n_2$ , $k$ 's prime factors can be divided into two groups according to whether they are prime factors of $n_1$ or $n_2$ . Multiplying the prime factors, with multiplicity, in the two groups separately gives $k_1$ and $k_2$ , which range over the divisors of $n_1$ and $n_2$ , respectively. Conversely, given divisors $k_1$ and $k_2$ of $n_1$ and $n_2$ , we can always obtain the divisor $k=k_1k_2$ of $n_1n_2$ . For the second claim, let $g=f^{-1}$ and apply mathematical induction. First, $g(1)=1/f(1)=1$ . The recurrence for the inverse can then be written as

g(n) = \varepsilon(n) - \sum_{k\ell = n,~k\neq 1} f(k)g(\ell).

Thus, for $n_1\perp n_2$ with $n_1n_2 > 1$ , we have

\begin{aligned} g(n_1n_2) &= -\sum_{k\ell=n_1n_2,~k\neq 1}f(k)g(\ell) \\ &= -\sum_{k_1\ell_1=n_1,~k_2\ell_2=n_2,~k_1k_2\neq 1}f(k_1)f(k_2)g(\ell_1)g(\ell_2)\\ &= f(1)f(1)g(n_1)g(n_2) - \sum_{k_1\ell_1=n_1,~k_2\ell_2=n_2}f(k_1)f(k_2)g(\ell_1)g(\ell_2)\\ &= g(n_1)g(n_2) - \left(\sum_{k_1\ell_1=n_1}f(k_1)g(\ell_1)\right)\left(\sum_{k_2\ell_2=n_2}f(k_2)g(\ell_2)\right) \\ &= g(n_1)g(n_2) - \varepsilon(n_1)\varepsilon(n_2)\\ &= g(n_1)g(n_2). \end{aligned}

The second equality uses the induction hypothesis: for $\ell_1\ell_2 < n_1n_2$ with $\ell_1\perp\ell_2$ , the condition $g(\ell_1\ell_2)=g(\ell_1)g(\ell_2)$ holds.

In the language of abstract algebra, all multiplicative functions form a subgroup of the multiplicative group of the Dirichlet ring.

An even more special class is that of completely multiplicative functions.

Theorem

Let $\alpha$ be a completely multiplicative function, and let $f,g$ be arithmetic functions. Then:

Distributivity: $(\alpha f)\ast(\alpha g) = \alpha\cdot(f\ast g)$ .
Inverse: $(\alpha f)^{-1}=\alpha f^{-1}$ , provided that $f^{-1}$ exists.
A multiplicative function $f$ is completely multiplicative if and only if $f^{-1}=\mu f$ , where $\mu$ is the Möbius function.

Proof

For the first statement, direct verification gives

\begin{aligned} ((\alpha f)\ast(\alpha g))(n) &= \sum_{k\ell = n}(\alpha f)(k)(\alpha g)(\ell) \\ &= \sum_{k\ell = n}\alpha(k)f(k)\alpha(\ell)g(\ell) \\ &= \sum_{k\ell = n}\alpha(n)f(k)g(\ell) \\ &= \alpha(n)(f\ast g)(n). \end{aligned}

The third equality uses the property of completely multiplicative functions that $\alpha(n)=\alpha(k)\alpha(\ell)$ for every $n=k\ell$ .

For the second statement, the first statement gives

(\alpha f)\ast(\alpha f^{-1}) = \alpha(f\ast f^{-1}) = \alpha\varepsilon = \varepsilon.

Here, the last equality uses only $\alpha(1)=1$ . By the definition of the inverse, $(\alpha f)^{-1}=\alpha f^{-1}$ .

For the third statement, using the second statement and $1^{-1}=\mu$ , if $f$ is completely multiplicative, then

f^{-1} = (1f)^{-1} = 1^{-1}\cdot f = \mu f.

Here, $1$ is the constant function. Conversely, if $f$ is multiplicative and $f^{-1}=\mu f$ , it is enough to prove that $f(p^e)=f(p)^e$ for every prime $p$ and $e\in\mathbf N_+$ in order to prove that $f$ is completely multiplicative. To this end, apply mathematical induction on $e\in\mathbf N_+$ . The statement is obvious at the base case $e=1$ . For any $e > 1$ , the inverse recurrence gives

\begin{aligned} f^{-1}(p^e) &= -\sum_{i=1}^{e}f(p^i)f^{-1}(p^{e-i}) \\ &= -\sum_{i=1}^{e}f(p^i)\mu(p^{e-i})f(p^{e-i})\\ &= -f(p^e)f(1)\mu(1) - f(p^{e-1})\mu(p)f(p)\\ &= -f(p^e) + f(p)^e. \end{aligned}

The last equality uses the induction hypothesis $f(p^{e-1})=f(p)^{e-1}$ . Applying $f^{-1}=\mu f$ gives

f^{-1}(p^e) = \mu(p^e)f(p^e) = 0.

Substituting into the previous equation gives

f(p^e) = f(p)^e.

Thus, the induction step holds, and the original statement follows.

In the language of abstract algebra, if $\alpha$ is completely multiplicative, the map $f\mapsto \alpha f$ is an endomorphism of the Dirichlet ring.

Dirichlet generating functions

Closely related to Dirichlet convolution are Dirichlet generating functions.

The Dirichlet generating function (Dirichlet series generating function, DGF) corresponding to an arithmetic function $f(n)$ —that is, the sequence $\{f(n)\}$ —is defined as the formal Dirichlet series (formal Dirichlet series):

F(s) = \sum_{n=1}^{\infty}\dfrac{f(n)}{n^s}.

The $s$ in the series is a formal variable. In common Dirichlet generating functions, $s$ can often be regarded as a complex variable, allowing one to study the analytic properties of Dirichlet series, but this lies beyond the scope of algorithmic competitions.

The product of Dirichlet generating functions corresponds to the Dirichlet convolution of the associated arithmetic functions:

Theorem

For arithmetic functions $f,g$ and their Dirichlet generating functions $F,G$ , the generating function of their Dirichlet convolution $f\ast g$ is $F\cdot G$ .

Proof

Direct verification:

\begin{aligned} F(s)G(s) &= \left(\sum_{k=1}^\infty\dfrac{f(k)}{k^s}\right)\left(\sum_{\ell=1}^\infty\dfrac{g(\ell)}{\ell^s}\right)= \sum_{k=1}^\infty\sum_{\ell=1}^\infty\dfrac{f(k)g(\ell)}{(k\ell)^s}\\ &= \sum_{n=1}^{\infty}\dfrac{\sum_{k\ell = n}f(k)g(\ell)}{n^s} = \sum_{n=1}^\infty\dfrac{(f\ast g)(n)}{n^s}. \end{aligned}

Using the correspondence between Dirichlet convolution and products of Dirichlet generating functions, we can understand the properties of Dirichlet convolution from the perspective of Dirichlet generating functions. Since multiplication of formal Dirichlet series satisfies commutativity, associativity, and distributivity over addition, Dirichlet convolution of arithmetic functions satisfies the same algebraic properties.

Euler products

The special nature of multiplicative functions is also reflected in Dirichlet generating functions. Since integers have the unique factorization theorem, the generating function $F(s)$ of a multiplicative function $f(n)$ can be written as follows:

\begin{aligned} F(s) &= \sum_{n=1}^{\infty}\dfrac{f(n)}{n^s} = \sum_{n=1}^{\infty}\prod_{p\in\mathbf P}\dfrac{f(p^{e})}{p^{es}} = \prod_{p\in\mathbf P}\sum_{e=0}^{\infty}\dfrac{f(p^e)}{p^{es}}\\ &= \prod_{p\in\mathbf P}\left(1 + \dfrac{f(p)}{p^s} + \dfrac{f(p^2)}{p^{2s}} + \dfrac{f(p^3)}{p^{3s}} + \cdots\right). \end{aligned}

This means that $F(s)$ can be decomposed into a product of several $F_p(s)$ , where the arithmetic function corresponding to each $F_p(s)$ can be nonzero only at powers of $p$ . This infinite product is also called an Euler product (Euler product). If both $F(s)$ and $G(s)$ can be decomposed in this form, then so can their product; translated back to arithmetic functions, this observation says that the Dirichlet convolution of multiplicative functions is still multiplicative.

Furthermore, if $f(n)$ is also completely multiplicative, then $f(p^e)=f(p)^e$ , and the above expression can be simplified further:

F(s) = \prod_{p\in\mathbf P}\sum_{e=0}^{\infty}\dfrac{f(p)^e}{p^{es}} = \prod_{p\in\mathbf P}\left(1-\dfrac{f(p)}{p^s}\right)^{-1}.

Unlike multiplicative functions, the forms of Dirichlet generating functions of completely multiplicative functions are not closed under multiplication. Therefore, the Dirichlet convolution and Dirichlet inverse of completely multiplicative functions need not be completely multiplicative, although they are always multiplicative.

Examples

The identity function $\varepsilon(n)$ is completely multiplicative. Its Dirichlet generating function is the constant function of the formal variable $s$
$E(s) = \sum_{n=1}^{\infty}\dfrac{\varepsilon(n)}{n^s} = 1.$
The constant function $1(n)$ is completely multiplicative. Its Dirichlet generating function is the Riemann zeta function
$I(s) = \sum_{n=1}^{\infty}\dfrac{1}{n^s} = \prod_{p\in\mathbf P}\dfrac{1}{1-p^{-s}} = \zeta(s).$
The Möbius function $\mu(n)$ is the Dirichlet inverse of the constant function. Its Dirichlet generating function is the reciprocal of $\zeta(s)$ :
$M(s) = \sum_{n=1}^{\infty}\dfrac{\mu(n)}{n^s} = \prod_{p\in\mathbf P}(1-p^{-s}) = \dfrac{1}{\zeta(s)}.$
The power function $\operatorname{id}_k(n)=n^k$ is completely multiplicative. In particular, when $k=0$ , it is the constant function; when $k=1$ , it is the identity function. Its Dirichlet generating function is
$I_k(s) = \sum_{n=1}^{\infty}\dfrac{n^k}{n^s} = \prod_{p\in\mathbf P}\dfrac{1}{1-p^{k-s}} = \zeta(s-k).$
Euler's totient function $\varphi(n)$ is multiplicative. Its Dirichlet generating function is
$\begin{aligned} \Phi(s) &= \prod_{p\in\mathbf P}\left(1+\dfrac{p-1}{p^s} + \dfrac{p(p-1)}{p^{2s}} + \dfrac{p^2(p-1)}{p^{3s}}+\cdots\right)\\ &= \prod_{p\in\mathbf P}\left(\dfrac{1}{1-p^{1-s}}-\dfrac{1}{p^s}\dfrac{1}{1-p^{1-s}}\right) = \prod_{p\in\mathbf P}\dfrac{1-p^{-s}}{1-p^{1-s}} = \dfrac{\zeta(s-1)}{\zeta(s)}. \end{aligned}$
Combining this with the Dirichlet expression for the power function gives $\mathrm{id} = \varphi\ast 1$ .
The divisor function $\sigma_k(n)=\sum_{d\mid n}d^k$ is multiplicative. Its Dirichlet generating function is
$\begin{aligned} \Sigma_k(s) &= \prod_{p\in\mathbf P}\left(1+\dfrac{1+p^k}{p^s}+\dfrac{1+p^k+p^{2k}}{p^{2s}}+\dfrac{1+p^k+p^{2k}+p^{3k}}{p^{3s}}+\cdots\right) \\ &= \prod_{p\in\mathbf P}\dfrac{1}{1-p^k}\left((1-p^k)+\dfrac{1-p^{2k}}{p^s}+\dfrac{1-p^{3k}}{p^{2s}}+\dfrac{1-p^{4k}}{p^{3k}}+\cdots\right)\\ &= \prod_{p\in\mathbf P}\dfrac{1}{1-p^k}\left(\dfrac{1}{1-p^{-s}} - \dfrac{p^k}{1-p^{k-s}}\right)\\ &= \prod_{p\in\mathbf P}\dfrac{1}{(1-p^{-s})(1-p^{k-s})} = \zeta(s-k)\zeta(s). \end{aligned}$
Combining this with the Dirichlet expression for the power function gives $\sigma_k = \mathrm{id}_k\ast 1$ . This is exactly the defining formula for $\sigma_k$ .
The indicator function $u(n)=|\mu(n)|$ of square-free numbers is multiplicative. Its Dirichlet generating function is
$U(s) = \prod_{p\in\mathbf P}(1+p^{-s}) = \prod_{p\in\mathbf P}\dfrac{1-p^{-2s}}{1-p^{-s}} = \dfrac{\zeta(s)}{\zeta(2s)}.$

Applications

Dirichlet generating functions can be used to express multiplicative functions as Dirichlet convolutions.

For example, in the process of the Du Jiao sieve, to compute the prefix sum of a multiplicative function $f$ , we need to find another multiplicative function $g$ such that both $f\ast g$ and $g$ have prefix sums that can be computed quickly. This process can be derived using Dirichlet generating functions.

Taking the example Luogu P3768 Simple Mathematical Problem from the Du Jiao sieve section, we need to construct an arithmetic function $g(n)$ satisfying the conditions above for $f(n)=n^2\varphi(n)$ . Since $f$ is multiplicative, its Dirichlet generating function is

F(s) = \prod_{p\in\mathbf P}\left(1 + \sum_{k=1}^{\infty}\dfrac{p^{3k-1}(p-1)}{p^{ks}}\right) = \prod_{p\in\mathbf P}\dfrac{1-p^{2-s}}{1-p^{3-s}} = \dfrac{\zeta(s-3)}{\zeta(s-2)}.

Comparing this with the Dirichlet generating function of the power function, we see that taking $g = \mathrm{id}_2$ gives $f \ast g = \mathrm{id}_3$ . Both prefix sums can be computed quickly.

Computing Dirichlet convolution

This section discusses computing Dirichlet convolution: given the sequences $\{f(k)\}_{k=1}^n$ and $\{g(k)\}_{k=1}^n$ , find the first several terms $\{h(k)\}_{k=1}^n$ of the Dirichlet convolution $h=f\ast g$ . The complexity of the algorithm varies slightly depending on the properties of the functions involved.

General case

If $f,g,h$ have no special properties, Dirichlet convolution can only be computed from its definition:

h(n) = \sum_{k\ell = n}f(k)g(\ell).

Enumerate $k$ and $\ell$ , and add the contribution $f(k)g(\ell)$ to $h(k\ell)$ . The enumeration complexity is

O\left(\sum_{k=1}^{n}\dfrac{n}{k}\right) = O(n\log n).

The reference implementation is as follows:

Reference Implementation

// Compute the Dirichlet convolution h = f * g.
auto dirichlet_convolute(const std::vector<int>& f, const std::vector<int>& g) {
  int n = f.size() - 1;
  std::vector<int> h(n + 1);
  for (int k = 1; k <= n; ++k) {
    for (int d = 1; k * d <= n; ++d) {
      h[k * d] += f[k] * g[d];
    }
  }
  return h;
}

Case of convolution with a multiplicative function

If $g$ is multiplicative, the computation of Dirichlet convolution can be accelerated using the Euler product. Computing $h$ is equivalent to computing the coefficients of its Dirichlet generating function $H$ . Since

H(s) = F(s)G(s) = F(s)\prod_{p\in\mathbf P}G_p(s).

Here, $G_p(s)$ is a factor in the Euler product decomposition of $G(s)$ ; it contains only the coefficients at powers of $p$ :

G_p(s) = \sum_{p^k\le n}\dfrac{f(p^k)}{p^{ks}} = 1 + \dfrac{f(p)}{p^s} + \dfrac{f(p^2)}{p^{2s}} + \cdots.

Starting with $F(s)$ , we can traverse every prime $p$ not exceeding $n$ and multiply by $G_p(s)$ one by one to obtain the final result $H(s)$ . When multiplying by $G_p(s)$ , we can directly apply the brute-force enumeration algorithm from the general case. The total number of enumerations is

\sum_{p\in\mathbf P,~p\le n}\sum_{k=1}^{\infty}\left\lfloor\dfrac{n}{p^k}\right\rfloor \le \sum_{p\in\mathbf P,~p\le n}\dfrac{n}{p-1} \le \sum_{p\in\mathbf P,~p\le n}\dfrac{2n}{p} \in O(n\log\log n).

The complexity estimate in the last step is the same as the proof of the complexity of the Sieve of Eratosthenes. Therefore, the time complexity of this algorithm is $O(n\log\log n)$ .

The reference implementation is as follows:

Reference Implementation

// Compute the Dirichlet convolution h = f * g.
// Assume that g is multiplicative.
auto dirichlet_convolute(const std::vector<int>& f, const std::vector<int>& g) {
  int n = f.size() - 1;
  std::vector<int> h(f);
  std::vector<bool> vis(n + 1);
  for (int i = 2; i <= n; ++i) {
    if (vis[i]) continue;
    // Reverse the order for in-place computation.
    for (int k = n / i * i; k; k -= i) {
      vis[k] = true;
      int d = k;
      while (true) {
        d /= i;
        h[k] += h[d] * g[k / d];
        if (d % i) break;
      }
    }
  }
  return h;
}

In particular, when the multiplicative function $g$ is completely multiplicative or is a Dirichlet inverse, such as when $g = 1$ or $g = \mu$ , the algorithm can be simplified further. In this case, the Dirichlet convolution $h = f\ast g$ can be computed using the Dirichlet prefix-sum/difference algorithm with a smaller constant, but the time complexity remains $O(n\log\log n)$ .

Case where the result is multiplicative

Finally, consider the case where $h$ is multiplicative. In particular, when both $f,g$ are multiplicative, $h=f \ast g$ is multiplicative. To compute $h$ , it is enough to determine its values at prime powers, after which it can be computed in $O(n)$ time using the linear sieve. For a prime power $p^e$ , the value $h(p^e)$ can be computed by brute force directly:

h(p^e) = \sum_{i=0}^e f(p^i)g(p^{e-i}).

The number of iterations required for these brute-force computations is

\begin{aligned} \sum_{p\in\mathbf P,~p\le n}\sum_{e=1}^{\lfloor\log_p n\rfloor}(e+1) &\le \sum_{p\in\mathbf P,~p\le\sqrt{n}}\lfloor\log_p n\rfloor^2 + \sum_{p\in\mathbf P,~\sqrt{n} < p\le n}1 \\ &\le \sqrt{n}(\log_2 n)^2 + n \in O(n). \end{aligned}

Therefore, the total time complexity of this algorithm is $O(n)$ .

The reference implementation is as follows:

Reference Implementation

// Compute the Dirichlet convolution h = f * g.
// Assume that h is multiplicative.
auto dirichlet_convolute(const std::vector<int>& f, const std::vector<int>& g) {
  int n = f.size() - 1;
  std::vector<int> h(n + 1), primes, rem(n + 1), lpf(n + 1);
  std::vector<bool> vis(n + 1);
  h[1] = 1;
  for (int x = 2; x <= n; ++x) {
    if (!vis[x]) {
      primes.push_back(x);
      rem[x] = 1;
      lpf[x] = x;
    }
    for (int p : primes) {
      if (x * p > n) break;
      vis[x * p] = true;
      rem[x * p] = x % p ? x : rem[x];
      lpf[x * p] = p;
      if (x % p == 0) break;
    }
    if (rem[x] == 1) {  // prime powers.
      for (int k = x; k; k /= lpf[x]) {
        h[x] += f[k] * g[x / k];
      }
    } else {  // other cases.
      h[x] = h[rem[x]] * h[x / rem[x]];
    }
  }
  return h;
}

Dirichlet Convolution

Dirichlet convolution

Properties

Dirichlet generating functions

Euler products

Applications

Computing Dirichlet convolution

General case

Case of convolution with a multiplicative function

Case where the result is multiplicative

References and notes