【杂】数论小总结

常见的数论函数

• 恒等函数： $I(n) = 1$

• 元函数： $\epsilon(n) = [n = 1]$

• 单位函数： $id(n) = n$

• 除数函数：输出函数用 $\sigma_k(n)$ 表示 $n$ 的 $k$ 次方的的和，即 $\sigma_k(n) = \sum\limits_{d | n} d^k$。

  • 约数个数函数，即 $\sigma_0(n)$，通常用 $d(n)$ 表示： $d(n) = \sum\limits_{d | n} 1$

  • 约数和函数，即 $\sigma_1(n)$，通常用 $\sigma(n)$ 表示： $\sigma(n) = \sum\limits_{d | n}d$

• 欧拉函数： $\varphi(n)$ 表示不大于 $n$ 且与 $n$ 互质的正整数个数。（注：$\varphi(1) = 1$）

• 莫比乌斯函数：

$$\mu(n)=\left\{ \begin{aligned} & 1 && n = 1 \\ & (-1)^s && n = p_1p_2p_3···p_s \\ & 0 && otherwise \end{aligned} \right.$$

附线性筛欧拉函数和莫比乌斯函数的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

inline void euler(){
    phi[1] = mu[1] = 1;
    for(ll i = 2; i < N; ++i){
        if(!vis[i]) phi[i] = i - 1, mu[i] = -1, p[++tot] = i;
        for(ll j = 1; j <= tot && i * p[j] < N; ++j){
            vis[i * p[j]] = 1;
            if(i % p[j] != 0) phi[i * p[j]] = phi[i] * (p[j] - 1), mu[i * p[j]] = -mu[i];
            else{
                phi[i * p[j]] = phi[i] * p[j], mu[i * p[j]] = 0;
                break;
            }
        }
    }
}

$Dirichlet$ 卷积

设 $f$，$g$ 是数论函数。

$$h(n) = \sum\limits_{d | n}f(d)g(\frac nd)$$

同样也可以写成：

$$h(n) = \sum\limits_{d | n}f(\frac nd)g(d)$$

则称 $h$ 为 $f$ 与 $g$ 的 $Dirichlet$ 卷积，记为：$h = f * g$

一些性质

• 交换律： $f * g = g * f$
• 结合律： $(f * g) * h = f * (g * h)$
• 分配律： $(f + g) * h = f * h + g * h$

一些小结论

• $$n = \sum\limits_{d | n}\varphi(d)$$

• $$d(ij) = \sum\limits_{x | i}\sum\limits_{y | j}[gcd(x, y) = 1]$$

• $$\sum\limits_{d | n}\mu(d) = [n = 1]$$

  这条性质也可以用卷积的形式来写： $\mu * I = \epsilon$

• $$f * \epsilon = f$$

• $$\sum\limits_{i = 1}^{n}\sum\limits_{j = 1}^{m}gcd(i, j) = \sum\limits_{k = 1}^{n}$$