Dirichlet Convolution

Dirichlet convolution is a binary operation defined between arithmetic functions. It can be expressed as \((f * g)(n) = \sum_{xy = n} f(x) \cdot g(y)\) or equivalently \((f * g)(n) = \sum_{d \mid n} f(d) \cdot g(\frac{n}{d})\).

Properties

1. If both \(f\) and \(g\) are multiplicative functions, then \(f * g\) is also multiplicative.
2. If both \(g\) and \(f * g\) are multiplicative, then \(f\) is multiplicative.
3. The Dirichlet inverse of a multiplicative function is also multiplicative.

Common Convolution Identities

• \(\operatorname{Id_k} * \mathbf{1} = \sigma_k\)
• \(\varphi * \mathbf{1} = \operatorname{Id}\)
• \(\mu * \mathbf{1} = \epsilon\)
• \(\mu * \operatorname{Id} = \varphi\)
• \((\mathbf{1} * \mathbf{1})(n) = \mathbf{d}(n)\)
• \(\sigma_0 * \mu = \mathbf{1}\)

Dirichlet Hyperbola Method

The Dirichlet hyperbola method is a technique for computing prefix sums of multiplicative functions over large ranges in sublinear time.

For an arithmetic function \(f\), we want to compute its prefix sum \(S\). We construct two auxiliary functions \(g\) and \(h = f * g\).

From convolution properties: \(\sum_{i = 1}^n h(i) = \sum_{i = 1}^n g(i) S(\frac{n}{i})\)

Isolating the \(i = 1\) term and rearranging gives:

\(g(1) \cdot S(n) = \sum_{i = 1}^n h(i) - \sum_{i = 2} g(i) S(\frac{n}{i})\)

The complexity is \(O(n^{\frac{3}{4}})\) for naive computation, which can be optimized to \(O(n^{\frac{2}{3}})\) by precomputing initial values and using memoization.

Computing Möbius Function

Using \(\mu * I = \epsilon\), we set \(f = \mu, g = I, h = \epsilon\):

long long compute_mu(int n) {
    if (n <= MAX_PRE) return precomputed_mu[n];
    if (memo_mu.count(n)) return memo_mu[n];
    long long result = 1;
    for (int left = 2, right; left <= n; left = right + 1) {
        right = n / (n / left);
        result -= (right - left + 1) * compute_mu(n / left);
    }
    return memo_mu[n] = result;
}

Computing Euler Totient Function

Using \(\varphi * I = \operatorname{Id}\), we set \(f = \varphi, g = I, h = \operatorname{Id}\):

long long compute_phi(int n) {
    if (n <= MAX_PRE) return precomputed_phi[n];
    if (memo_phi.count(n)) return memo_phi[n];
    long long result = 1LL * n * (n + 1LL) / 2LL;
    for (int left = 2, right; left <= n; left = right + 1) {
        right = n / (n / left);
        result -= (right - left + 1) * compute_phi(n / left);
    }
    return memo_phi[n] = result;
}

Möbius Inversion

Möbius inversion is a technique that uses convolution relationships between arithmetic functions to simplify expressions.

Iverson Bracket and Division Trick

The Iverson bracket \([P]\) equals 1 when proposition \(P\) is true, and 0 otherwise.

For division trick: values of \(\frac{n}{i}\) form \(O(\sqrt{n})\) contiguous blocks. For value at \(x\), the right endpoint of its block is \(\lfloor \frac{n}{\lfloor \frac{n}{x} \rfloor} \rfloor\).

Inversion Formulas

If \(F(n) = \sum_{d \mid n} f(d)\), then \(F = I * f\). Multiplying by \(I^{-1} = \mu\) gives:

1. \([n = 1] = \sum_{d \mid n} \mu(d)\)
2. If \(F(n) = \sum_{d \mid n} f(d)\), then \(f(n) = \sum_{d \mid n} F(d) \mu(\frac{n}{d}) = \sum_{d \mid n} F(\frac{n}{d}) \mu(d)\)
3. If \(F(n) = \sum_{n \mid d} f(d)\), then \(f(n) = \sum_{n \mid d} F(d) \mu(\frac{d}{n})\)

Practical Techniques

Summation Transformations

• \(\sum_{i=1}^n \sum_{j=1}^m \sum_{d \mid \gcd(i,j)} \mu(d) \rightarrow \sum_{d=1}^{\min(n,m)} \mu(d) \lfloor \frac{n}{d} \rfloor \lfloor \frac{m}{d} \rfloor\)
• \(\sum_{i=1}^n \sum_{j=1}^m [\gcd(i,j) = k] \rightarrow \sum_{i=1}^{\lfloor \frac{n}{k} \rfloor} \sum_{j=1}^{\lfloor \frac{m}{k} \rfloor} [\gcd(i,j) = 1]\)
• Variable substitution: \(\sum_{d=1}^n \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} f(\frac{n}{id}) \rightarow \sum_{T=1}^n \sum_{d \mid T} f(\frac{n}{T})\)

Useful Identities

• \(\sum_{i=1}^n i = \frac{n(n+1)}{2}\)
• \(\sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6}\)
• \(\varphi\) inversion: \(x = \sum_{d \mid x} \varphi(d)\)
• Integer points on line segment: \(\gcd(|a-c|, |b-d|) + 1\)

Optimization Strategies

• Use \(\mu\) as inclusion-exclusion coefficeints for square-free counting
• Transform products into sums by considering exponents
• For multiple queries, use offline processing with data structures
• Common approach: \(O(n \ln n \log n)\) with Fenwick trees, updating multiples