数论函数总结

——数论函数就是研究正整数性质的函数

——在数论上，指定义域为正整数、陪域为复数的函数

---

参考博客:基础数论复习，数论函数（一）

本文主要包含以下几个数论函数及其性质 ：

$$\varphi(x)\space \space \space \mu(x)\space \space \space id^k(x)\space \space \space \tau(x)\space \space \space \sigma(x)\space \space \space \varepsilon(x)\space \space \space$$

一、欧拉函数 $\varphi(n)$

定义

小于$x$的正整数中与x互质的数的个数，即 ：

$$\varphi(n) \sum_{i<n}[i \perp x]$$

（任何数都与 $1$ 互质） 其中约定$\varphi(1) = 1$

性质

1. 对于质数 $p$ ，$\varphi(p) = p-1$ 显然，除了质数本身的数都与他互质
2. 对于 $x = p^k,k \in N_{+}$,有 $\varphi(x) = (p-1) \times p^{k-1}$ 证明 ： 所有 $p$ 的倍数都与 $x$ 不互质，其他所有数都与 $x$ 互质，$1 \sim x$ 中 $p$ 的倍数恰好有 $p^{k-1}$ 个（包括 $x$），所以 $\varphi(x) = p^k - p^{k-1} = (p-1) \times p^{k-1}$
3. 欧拉函数是积性函数，即对于互质的两数 $p$ ， $q$ ，有 $\varphi(p \times q) = \varphi(p) \times \varphi(q)$ 证明略
4. 对于数 $x$ 分解质因数的结果是 $x = \prod_{i = 1}^{n} p_i^{k_i}$ ，有 $\varphi(x) = x \prod_{i = 1}^{n} (1 - \frac{1}{p_i} )$。显然利用该性质可以在 $O(\sqrt{n})$ 的时间内容易地求出数 $n$ 的欧拉函数值。 证明 ： 利用前几条定理代入即得
5. 若 $p \mid x \ \&\&\ p\in prime$ ，有 $\varphi(p \times x) = p \times \varphi(x)$ 证明 ： 使用性质4，连乘内容不变，前面 $x$ 变成 $p \times x$ 即得
6. 若 $p \nmid x \ \&\&\ p \in prime$，有 $\varphi(p \times x) = (p-1) \times \varphi(x)$ 证明 ： $p$ 与 $x$ 互质，由积性函数得到
7. $\varphi * 1 = id$
8. 当 $n > 1$ 时，$1 \sim n$ 中与 $n$ 互质的整数和为 $\frac{n \cdot \varphi(n)}{2}$

预处理

对于单个欧拉函数求解可利用性质4分解质因数后求解 线性求欧拉函数则需要改一改欧拉筛，利用性质5、6求解 ： 筛去合数时，已知质数i为其约数，判断p[j]是否为i的约数，由性质5、6求解。

使用欧拉筛线性预处理 ：

void euler_phi(int n)
{
    phi[1] = 1;
    vis[0] = vis[1] = 1;
    for(int i = 2;i<=n;i++)
    {
        if(!vis[i]) {p[++tot] = i;phi[i] = i-1;}
        for(int 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];
                break;
            }
            phi[i * p[j]] = phi[i] * (p[j]-1);
        }
    }
}

使用杜教筛亚线性求前缀和 ：

ll S_phi(ll n)
{
    if(n < N) return sum_phi[n]; // 线性筛预处理出来的内容
    if(mp_phi.count(n)) return mp_phi[n]; // 记忆化的内容
    ll res = 1ll * n * (n + 1) / 2; // id 的前缀和
    for(ll l = 2,r;l<=n;l = r + 1)
    {
        r = n / (n / l);
        res -= S_mu(n / l) * (r - l + 1); // 1在l到r的和就是 r - l + 1
    }
    return mp_mu[n] = res; // 记忆化
}

应用

扩展欧拉定理 ：

$$a^{b} \equiv\left\{\begin{array}{ll} a^{b \bmod \varphi(p)} & a \perp p \\ a^{b} & a \not \perp p, b<\varphi(p) \quad(\bmod p) \\ a^{b \bmod \varphi(p)+\varphi(p)} & a \not \perp p, b \geq \varphi(p) \end{array}\right.$$

证明……这个 可以降幂用，比方说luogu上头那道古代猪文

---

二、莫比乌斯函数 $\mu(n)$

定义

$$\mu(n)=\begin{cases} 1, & n=1 \\ (-1)^{k}, & n=p_{1} \cdot p_{2} \cdot \ldots \cdot p_{k} \\ 0, & \text{otherwise} \end{cases}$$

性质

1. 积性函数
2. 与欧拉函数 ：

$$\sum_{d \mid n}\frac{\mu(d)}{d} = \frac{\varphi(n)}{n}$$

3. 与组合数 ：

$$\sum_{d \mid n} \mu(d)=\sum_{i=0}^{k}\left(\begin{array}{l} k \\ i \end{array}\right) \cdot(-1)^{i}=\left\{\begin{array}{l} 1, n=1 \\ 0, n>1 \end{array}\right.$$

4. $\mu * 1 = \varepsilon$

$$\sum_{d \mid n} \mu(d) = \begin{cases} 1 & n = 1\\ 0 & n \neq 1 \end{cases}$$

5. $id * \mu = \varphi$
6. 无穷级数（没见用过） ：

$$\begin{aligned} \sum_{n = 1}^{\infty} \frac{\mu(n)}{n} &= 0 \\ \sum_{n = 1}^{\infty} \frac{\mu(n) \cdot \ln(n)}{n} &= -1 \\ \sum_{n = 1}^{\infty} \frac{\mu(n) \cdot x^n}{1-x^n} &= x \end{aligned}$$

预处理

使用欧拉筛线性预处理 ：

void euler_mu(int n)
{
    mu[1] = 1;
    vis[0] = vis[1] = 1;
    for(int i = 2;i<=n;i++)
    {
        if(!vis[i]) {p[++tot] = i;mu[i] = -1;}
        for(int j = 1;j<=tot && i * p[j]<=n;j++)
        {
            vis[i * p[j]] = 1;
            if(i % p[j] == 0) {
                mu[i * p[j]] = 0;
                break;
            }
            mu[i * p[j]] = -mu[i];
        }
    }
}

使用杜教筛亚线性求前缀和 ：

ll S_mu(ll n)
{
    if(n < N) return sum_mu[n]; // 线性筛预处理出来的内容
    if(mp_mu.count(n)) return mp_mu[n]; // 记忆化的内容
    ll res = 1; // 单位元的前缀和就是1
    for(ll l = 2,r;l<=n;l = r + 1)
    {
        r = n / (n / l);
        res -= S_mu(n / l) * (r - l + 1); // 1在l到r的和就是 r - l + 1
    }
    return mp_mu[n] = res;
}

三、幂函数 $id^k(n)$

定义

$$id^k(n) = n^k$$

（也称恒等函数） 特别地，当 $k = 1$ 时，$id(n) = n$ 被称为单位函数，当 $k = 0$ 时，函数变为 $1(n) = 1$ ，是常数函数

性质

1. 完全积性

四、因子个数函数 $\tau(n)$

也有很多地方记作 $\text{d}(n)$

定义

因子个数函数 $\tau$ 定义为正整数 $n$ 的所有正因子个数

$$\tau(n) = \sum_{i \mid n}1$$

或

$$\tau(n) = \sum_{i=1}^{n}[i\mid n]$$

性质

$$\tau(ij) = \sum_{x \mid i}\sum_{y \mid j}[\gcd(x,y) = 1]$$

证明 ：

证明来自Siyuan 的博客。

考虑把乘积的因子使用原数的因子唯一表示出来 ：

如果 $ij$ 的因子 $k$ 中有一个因子 $p^c$ ， $i$ 中有因子 $p^a$ ，$j$ 中有因子 $p^b$ 。 我们规定：

• 如果 $c \le a$ ，那么在 $i$ 中选择。
• 如果 $c > a$ ，那么 $j$ 中选择 $p^{c-a}$

使用这种方式我们对于 $ij$ 的任何因子 $k$ 都有一个唯一的映射，并且每一种选择方式对应着唯一一个 $k$ 。

通过如上过程，我们发现：对于 $ij$ 的因子 $k=\prod {p_i}^{c_i}$ ，我们不可能同时在 $i$ 和 $j$ 中选择 $p_i$ （优先在 $i$ 中选择，如果不够就只在 $j$ 中选择不够的指数），故 $x$ 和 $y$ 必须互质。

等式得证。

An_Account — 莫比乌斯反演-让我们从基础开始 当中有另一个通俗的解释 ：

其实，这里的 $gcd(i,j)=1$ 并不是为了去重，而是为了和左边的式子保持相等

我们考虑一个质数 $p$ ， $i=i'\ast p^{k_1},j=j'\ast p^{k_2}i=i$ ，注意这里 $k_1,k_2$ 可以为 $0$ 考虑$p$ 对 $d(i\ast j)$ 的贡献，显然，在 $d$ 的因子中，$p$ 的这一项可以为 $0 \sim k_1+k_2$ 共 $k_1+k_2+1$ 个。

考虑等式右边，我们只看 $p$ 这一项。$x=x' \ast p^{k_x},y=y'\ast p^{k_y}x=x$ 要满足 $\gcd(x,y)=1$ ,那么就有 $\gcd(p^{k_x},p^{k_y})=1$

要么 $k_x=0,k_y\in[0,k_2]$ ，共 $k_2+1$ 种

要么 $k_y=0,k_x\in[0,k_1]$ ，共 $k_1+1$ 种

减去重复判断的 $k_x=0,k_y=0$ 这种情况，最后答案$k_1+k_2+1$ 种。

与等式左边相同！

预处理

预处理参考自Star_Cried

预处理利用了约数个数定理。

$$n = \prod_{p_i \mid n} p_i^{k_i}$$

则 ：

$$\tau(n) = \prod(k_i+1)$$

我们设 $a_i$ 表示数 $i$ 的最小质因子的指数。

考察线性筛的过程，我们设 tmp = i * p[j] ，于是有如下转移 ：

• 对于一个质数 $p$，$a_p = 1,\tau(p) = 2$ (两个约数是显然约数)
• 当满足 i % p[j] == 0 时，我们已知 p[j] 是 tmp 的最小质因子，且多出现了一次，于是有 $a_{tmp} = a_i + 1$ ,同样更新 $\tau(tmp) = \tau(i) * \frac{a_{tmp}+1}{a_i+1}$ ，更新这个质因子的贡献。
• 否则此时的 p[j] 是新出现的最小质因子（只出现一次），$a_{tmp} = 1,\tau(tmp) = \tau(i)*2$

代码 ：

void euler_tau(int n)
{
    tau[1] = 1;
    for(int i = 2;i <= n;i++)
    {
        if(!vis[i]) p[++tot] = i,tau[i] = 2,a[i] = 1;
        for(int j = 1;j <= tot && i * p[j] <= n;j++)
        {
            int tmp = i * p[j];
            vis[tmp] = 1;
            if(i % p[j] == 0)
            {
                a[tmp] = a[i] + 1;
                tau[tmp] = tau[i] / (a[i] + 1) * (a[tmp] + 1);
                break;
            }
            a[tmp] = 1;
            tau[tmp] = tau[i] * 2;
        }
    }
}

在这现敲的，但是应该没问题（

五、除数函数 $\sigma(n)$

定义

$$\sigma_k(n) = \sum_{d\mid n}d^k$$

其中 $k = 0$ 时通常简记作 $d(n)$ 或 $\tau(n)$ ，即因子个数函数， $k = 1$ 时通常简记作 $\sigma(n)$

预处理参考自Star_Cried

预处理

仅举 $\sigma_1$ 为例 ：

可以使用线性筛预处理 $\sigma_1$

这里是计算式 ：

$$\sigma(n) = \prod_{p_i \mid n} \sum_{j = 0}^{k_i} p_i^j$$

设 $a_i$ 表示最小质因子各次幂的和，即 ：

$$a_i = \sum_{j = 0}^{k_i} p_i^{k_i}$$

考察线性筛的过程，我们设 tmp = i * p[j] ，于是有如下转移 ：

• 对于一个质数 $p$,根据定义有 $\sigma(p) = p+1,a_p = p+1$
• 当满足 i % p[j] == 0 时，我们已知 p[j] 是 tmp 的最小质因子，且多出现了一次，幂次加一。于是有 $a_{tmp} = a_i \ast p + 1$，可以认为是每个次幂右移之后加上常数项。对于 $\sigma$ 的转移类似对 $\tau$ 的转移 ： $\sigma(tmp) = \sigma(i) \ast \frac{a_{tmp}}{a_{i}}$
• 否则p[j]是唯一的最小质因子，转移 ： $a_{tmp} = p+1,\sigma(tmp) = \sigma(i) \ast \sigma(p)$，第二个转移可以由积性解释，也可以由计算式解释。等价于 $\sigma(tmp) = \sigma(i) \ast (p+1)$

代码 ：

void euler_sigma(int n)
{
    sigma[1] = 1;
    for(int i = 2;i <= n;i++)
    {
        if(!vis[i]) p[++tot] = i,sigma[i] = a[i] = i + 1;
        for(int j = 1;j <= tot && i * p[j] <= n;j++)
        {
            int tmp = i * p[j];
            vis[tmp] = 1;
            if(i % p[j] == 0)
            {
                a[tmp] = a[i] * p[j] + 1;
                sigma[tmp] = sigma[i] / a[i] * a[tmp];
                break;
            }
            a[tmp] = p[j] + 1;
            sigma[tmp] = sigma[i] * (p[j] + 1);
        }
    }
}

六、单位函数 $\varepsilon(n)$

定义

$$\varepsilon(n) = [n = 1]$$

性质

1. 完全积性

关于积性函数

定义

关于任意互质的正整数 $a,b$ 有 $f(ab) = f(a) * f(b)$ 的数论函数称为积性函数

其中假设去掉互质的限制，即数论函数 $f$ 满足对任意正整数 $a,b$ 有 $f(ab) = f(a) * f(b)$ ,那么 $f$ 称为完全积性函数。

性质

• 若 $f,g$ 为积性函数，那么 $h(n) = f(n)g(n)$ 也是积性函数
• 若 $f$ 为积性函数，那么 $g(n) = \sum_{d \mid n}f(d)$ 也是积性函数。积性函数的和函数也是积性函数。
• 两个积性函数的卷积也是积性函数。

应该没了（

by Pozhu 忘了哪天