数论函数合集

LuckyLuo-OI / 2023-08-13 / 原文

整除分块

例题：UVA11526 H(n)

复杂度保证：

\[\forall n \in\mathbb{N_+},|\{ \left \lfloor \frac{n}{i} \right \rfloor | \ i \in \mathbb {N_+},i \le n\}| \le \left \lfloor {2 \sqrt n} \right \rfloor \]

（来自oiwiki

重要结论：

对于 $\left \lfloor \frac{n}{a} \right \rfloor = \left \lfloor \frac{n}{b} \right \rfloor$ 成立的最大的 $b$ 为 $\left \lfloor \frac{n}{\left \lfloor \frac{n}{a} \right \rfloor} \right \rfloor $ 。

对于答案 $\sum_{i=1}^{n}f(i)g(\left \lfloor \frac{n}{i} \right \rfloor)$

设 $r = \left \lfloor \frac{n}{\left \lfloor \frac{n}{l} \right \rfloor} \right \rfloor$ ，$s(i) = \sum_{i=1}^n f(i)$ ；

区间 $[l, r]$ 的贡献即为 $(s(r) - s(l-1)) \times g(\left \lfloor \frac{n}{l} \right \rfloor) $

数论函数

积性函数：满足对于 $gcd(a,b)=1$ 的 $a, b$ 有 $f(ab)=f(a)f(b)$ 的数论函数。

完全积性函数：满足 $\forall a, b, f(ab)=f(a)f(b)$ 的数论函数

常见数论函数（都是积性函数）：

设 $n = \prod_{i=1}^c p_i^{k_i}$
$\epsilon(n) = [n=1]$ （完全）
$1(n)=1$ （完全）
$Id(n) = n$ （完全）
$d(n) = \sum_{d|n}1=\prod_{i=1}^c(k_i+1)$
$\sigma(n) = \sum_{d|n}d$
$\varphi(n)=\sum_{i=1}^n[gcd(i, n) = 1]= n \times \prod_{i=1}^c\frac{p_i-1}{p_i}$
$\mu(n)=[max_{i=1}^c k_i \le 1](-1)^c$

对于一个积性函数，求 $f(n)$ 需要知道所有的 $f(p_i^{k_i})$ ；

对于一个完全积性函数，求 $f(n)$ 需要知道所有的 $f(p_i)$ ；

数论卷积

定义两个数论函数 $f(n), g(n)$ 的卷积为 $h(n) = \sum_{d|n}f(d)g(\frac{n}{d})$ ，记作 $h = f * g$ 。

$\epsilon * f = f$
$1 * 1 = d$
$1 * Id = \sigma$
$1 * \varphi = Id$
$1 * \mu = \epsilon$

莫比乌斯反演

若 $g(n)=\sum_{d|n}f(d)$ ，则有 $f(n) = \sum_{d|n}\mu(\frac{n}d)g(d)$

$g = 1 * f \Rightarrow g * \mu = (1 * \mu) * f \Rightarrow f * \epsilon = g * \mu \Rightarrow f = g * \mu$

莫反拆gcd

经典应用，$f(n)$ 灵活使用，套用数论卷积 / 前缀和预处理 / 调和级数因数预处理，多测一次 / 二次整除分块

\[\sum_{i=1}^{n}\sum_{j=1}^{n} f(gcd(i, j)) \]
\[= \sum_{d=1}^n\sum_{i=1}^n\sum_{j=1}^nf(d)[gcd(i,j)=d] \]
\[=\sum_{d=1}^n\sum_{i=1}^{\left\lfloor\frac{n}d\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{n}d\right\rfloor}f(d)[gcd(i,j)=1] \]
\[=\sum_{d=1}^n\sum_{i=1}^{\left\lfloor\frac{n}d\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{n}d\right\rfloor}f(d) \sum_{k|gcd(i,j)}\mu(k) \]
\[=\sum_{d=1}^n\sum_{k=1}^{\left\lfloor\frac{n}d\right\rfloor} \mu(k) \sum_{i=1}^{\left\lfloor\frac{n}{dk}\right\rfloor} \sum_{j=1}^{\left\lfloor\frac{n}{dk}\right\rfloor}f(d) \]
\[=\sum_{d=1}^n\sum_{k=1}^{\left\lfloor\frac{n}d\right\rfloor} \mu(k)f(d) \left\lfloor\frac{n}{dk}\right\rfloor^2 \]
\[=\sum_{T=1}^n\sum_{d|T}f(d)\mu(\frac{T}d) \left\lfloor\frac{n}T\right\rfloor^2 \]

\[= \sum_{T=1}^n(f*\mu)(T)\left\lfloor\frac{n}T\right\rfloor^2 \]

Ex：

\[\sum_{i=1}^n\sum_{j=1}^n[gcd(i,j)=1] = \sum_{T=1}^n(\epsilon*\mu)(T) \left\lfloor\frac{n}T\right\rfloor^2 = \sum_{T=1}^n\mu(T) \left\lfloor\frac{n}T\right\rfloor^2 \]

\[\sum_{i=1}^n\sum_{j=1}^ngcd(i,j) = \sum_{T=1}^n(Id*\mu)(T) \left\lfloor\frac{n}T\right\rfloor^2 = \sum_{T=1}^n\varphi(T) \left\lfloor\frac{n}T\right\rfloor^2 \]