Learning Notes on Multiplicative Functions, Dirichlet Convolution, Mobius Inversion, etc

Common Functions
  • Unit Function: $\epsilon(n)=[n=1]$
  • Constant Function: $1(n)=1$
  • Euler Function: $\varphi(n)=\sum_{i=1}^n [\gcd(i,n)=1]$
  • Mobius Function:$ \mu(n)=\left\{
    \begin{aligned}
    1 & \text{, if $n=1$} \\
    0 & \text{, if $n$ has some square}\\
    (-1)^k & \text{, ($k$ is the number of prime divisors of $n$) otherwise}
    \end{aligned}
    \right.
    $
Dirichlet Convolution

$$ (f*g)(n)=\sum_{d\mid n}f(d)g(\frac{n}{d}) $$

Common Convolutions:
$$ \varepsilon=\mu * 1 \iff \varepsilon(n)=\sum_{d\mid n}\mu(d)$$ $$ d=1 * 1 \iff d(n)=\sum_{d\mid n}1 $$ $$ \sigma=d * 1 \iff \sigma (n)=\sum_{d\mid n}d$$ $$\varphi=\mu * \text{ID} \iff \varphi(n)=\sum_{d\mid n}d\cdot\mu(\frac{n}{d})$$


Mobius Inversion

The first form of Mobius Inversion:
$\displaystyle F(n)=\sum_{d|n}f(d)\implies f(n)=\sum_{d|n}\bigg(\mu(d)\cdot F\Big(\frac{n}{d}\Big)\bigg)$

Proof of the first form:
$\displaystyle \sum_{d|n}\bigg(\mu(d)\cdot F\Big(\frac{n}{d}\Big)\bigg)$ $=\sum_{d|n}\bigg(\mu(d)\cdot \sum_{k|\frac{n}{d}}f(k)\bigg)=\sum_{k|n}\bigg(f(k)\cdot \sum_{d|\frac{n}{k}}\mu(d)\bigg)=f(n)$

Second form:
$\displaystyle F(n)=\sum_{n|d}f(d)\implies f(n)=\sum_{n|d}\bigg(\mu\Big(\frac{d}{n}\Big)\cdot F(d)\bigg)$

Related Problems

Euler’s Functions/ Mobius Inversion: CF645F
Let $F[n]$($f[n]$) be the number of $k$-tuples the g.c.d. of whose numbers is a multiple of k (exactly k ), respectively. First we have $F[n] = {{cnt[n]}\choose{k}}$, where $cnt[n]$ is the number of species that has number divisible by $n$.
By Mobius Inversion, we have $f(d) = \sum_{d|n} \mu(\frac{n}{d}) F(n)$, and the answer for the problem equals $\sum_{d = 1}^{10^6} d \cdot f(d)$
$$= \sum_{d = 1}^{10^6} d \cdot \sum_{d|n} \mu(\frac{n}{d}) F(n) $$
We can change the summation to sum over $n$ instead, and then we have $$= \sum_{n = 1}^{10^6} \sum_{d|n} d \cdot \mu(\frac{n}{d}) F(n)$$ $$= \sum_{n = 1}^{10^6} F(n) \sum_{d|n} d \cdot \mu(\frac{n}{d}) $$ $$= \sum_{n = 1}^{10^6} F(n) \varphi(n)$$.
Therefore, each update can only affect $O(maxdivs)$ values of $F$, which is good enough for this problem.

Changing representation of the sequence: 1097F
In this problem, we can store the frequency of the multiples instead of the number itself. This is essentially Mobius Inversion, which is also a linear transformation, we can use bitwise xor for addition, and bitwise and for Cartisian product.

LCM: SPOJ LCMSUM
Key takeaways:
1. The formula $lcm(a, b) = \frac{a \cdot b}{gcd(a, b)}$ can turn the problem to some gcd-related stuff where we can apply Mobius Inversion.
2. TODO

No. of Divisors: CF235E
Let $d(x)$ be the number of divisors of $x$.
Then $ d(mn)=\sum\limits_{i|m}\sum\limits_{j|n}[(i,j)=1] $
Also, $d(r \cdot s \cdot t)=\sum\limits_{i|r}\sum\limits_{j|st}[(i,j)=1]=\sum\limits_{i|r}\sum\limits_{j|s}\sum\limits_{k|t}[(i,jk)=1][(j,k)=1]$ $=\sum\limits_{i|r}\sum\limits_{j|s}\sum\limits_{k|t}[(i,j)=1][(i,k)=1][(j,k)=1]$
Refer to this blog for more details.

Centroid Decomposition: CF809E
By enumerating the GCD, we need to calculate $$\sum_{i = 1}^{n} \frac{f_i \cdot i}{\varphi(i)}$$ where $$f_i = \sum_i \sum_j [(a_i, b_j) = g] \varphi (a_i) \varphi (b_j) d(i)$$. Instead of calculating $f_i$, we can calculate $g_d = \sum_{d | a_i} \sum_{d | b_j} \varphi (a_i) \varphi (b_j) d(i) $ by using centroid decomposition.

Total number of divisors of all the numbers is $O(n \log n)$ and each of them is used $O(\log n)$ because of centroid decomposition. So the total complexity is $O(n \log^2 n)$

Reference

Leave a Reply

Your email address will not be published. Required fields are marked *