数论函数总结

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

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

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

$\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$

性质

对于质数 $p$ ，$\varphi(p) = p-1$
显然，除了质数本身的数都与他互质
对于 $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}$
欧拉函数是积性函数，即对于互质的两数 $p$ ， $q$ ，有 $\varphi(p \times q) = \varphi(p) \times \varphi(q)$
证明略
对于数 $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$ 的欧拉函数值。
证明：利用前几条定理代入即得
若 $p \mid x \ \&\&\ p\in prime $ ，有 $ \varphi(p \times x) = p \times \varphi(x) $
证明：使用性质4，连乘内容不变，前面 $x$ 变成 $p \times x$ 即得
若 $p \nmid x \ \&\&\ p \in prime $，有 $\varphi(p \times x) = (p-1) \times \varphi(x) $
证明： $p$ 与 $x$ 互质，由积性函数得到
$\varphi * 1 = id$
当 $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)=\left\{\begin{array}{c} &1, &n=1 \\ &(-1)^{k}, &n=p_{1} \cdot p_{2} \cdot \ldots \cdot p_{k} \\ &0, &\text { otherwise } \end{array}\right.$

性质

积性函数
与欧拉函数： $\sum_{d \mid n}\frac{\mu(d)}{d} = \frac{\varphi(n)}{n}$
与组合数： $\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.$
$\mu * 1 = \varepsilon $ $\sum_{d \mid n} \mu(d) = \begin{cases} 1 & n = 1\\ 0 & n \neq 1 \end{cases}$
$id * \mu = \varphi $
无穷级数（没见用过）： $\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\\$

预处理

使用欧拉筛线性预处理：

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$ ，是常数函数

性质

完全积性

四、因子个数函数 $\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);
        }
    }
}