常见积性函数

定义

积性函数 指对于 任意互质的整数 $a$ 和 $b$ 有性质 $f(ab)=f(a)\times f(b)$ 的数论函数。

完全积性函数 指对于 任意整数 $a$ 和 $b$ 有性质 $f(ab)=f(a)\times f(b)$ 的数论函数。

很显然 完全积性函数 是 积性函数 的一个子集。

积性函数

欧拉函数

定义：

欧拉函数，属于 积性函数，但不是完全积性函数。常用 $\varphi$ 表示，读作 fai 。

$\varphi(n)$ 定义为小于等于 $n$ 的正整数中与 $n$ 互质的数的个数。

公式：

若 $p_1 , p_2 ,\ldots, p_m$ 为 $x$ 的所有 互不相同 的质因数，$n$ 是一个不为 $0$ 的整数，则

$$\begin{aligned} \varphi(n)&=n\times\left ( 1-\frac{1}{p_1}\right )\times \left ( 1-\frac{1}{p_2}\right )\times \cdots \times \left ( 1-\frac{1}{p_m}\right )\\[2ex] &=n\prod\limits_{i=1}^{m}\left ( 1-\frac{1}{p_i}\right )\\ \end{aligned}$$

性质 & 证明：

性质 1：

若 $n , m​$ 互质，则 $\varphi(nm)=\varphi(n) \times \varphi(m)​$ 。

证明：

积性函数特有性质。

性质 2：

若 $n​$ 为 质数，则 $\varphi(n)=n-1​$ 。

证明：

所有小于 $n$ 的正整数都与 $n$ 互质，一共 $n - 1​$ 个。

性质 3：

若 $n​$ 为 奇数，则 $\varphi(2n)=\varphi(n)​$ 。

证明：

显然 $n$ 与 $2$ 互质，且 $\varphi(2) = 1$，所以根据 性质 1，可得

$$\begin{aligned} \varphi(2n)&=\varphi(2) \times \varphi(n)\\[1ex] &=1\times \varphi(n)\\[1ex] &=\varphi(n) \end{aligned}$$

性质 4：

若 $p$ 为质数，$n = p^k$，则

$$\varphi(n)=p^k-p^{k-1}$$

证明：

由 $n=p^k$，得 $n$ 的质因数只有 $p$，再通过公式，可知

$$\begin{aligned} \varphi(n)&=n\times\left(1-\frac{1}{p}\right)\\[2ex] &=p^k \times \left(1-\frac{1}{p}\right)\\[2ex] &= p^k - p^{k-1} \end{aligned}$$

性质 5：

若 $n > 2​$，则 $\varphi(n)​$ 为偶数。

若 $n > 1$，则小于等于 $n$ 且与 $n$ 互质的数的和为

$$\frac{n \times \varphi(n)}{2}$$

证明：

首先需要知道：若 $n$ 与 $m$ 互质 $(n > m)$，则 $n$ 与 $n - m$ 互质。

$$\begin{aligned} &\gcd(n,m)=1\\[1ex] &\gcd(n,m)=\gcd(n,n-m)\\ \end{aligned}$$

显然与 $n$ 互质的数都是成对出现的，且相加的和为 $n$，只有在 $\gcd(n,\frac{n}{2})=1$ 时例外，但这种情况只会在 $n \leq 2$ 时出现，所以 $\varphi(n)\ (n > 2)$ 为偶数得证。小于等于 $n$ 的数中，与 $n$ 互质的数的个数为 $\varphi(n)$，所以一共有 $\frac{\varphi(n)}{2}$ 对，总和为 $\frac{n \times \varphi(n)}{2}​$。

性质 6：

若正整数 $x$ 与质数 $p$ 不互质

程序：

如何求出 $\varphi(n)​$ ？

根据欧拉函数的公式我们能够得到以下代码：

inline int getPhi(int n) {
    int res = n;
    for (int i = 2; i <= n; ++i)//枚举因数
        if (n % i == 0) {
            res -= res / i;
            for (; n % i == 0; n /= i);//将质因数 i 除完
        }
    return res;
}

在最坏情况下（$n​$ 是质数），该代码的时间复杂度为 $O(n)​$，这显然不够优秀，考虑如何优化。

任何一个整数 $n$ 都不可能存在 $2$ 个大于 $\sqrt n$ 的质因子，所以我们枚举因数时只需要遍历到 $O(\sqrt n)$ 即可，如果将小于 $\sqrt n$ 的质因子除完后，剩下的数不为 $1$，说明还有 $1$ 个大于 $\sqrt n$ 的质因子，最后要算进去。这种做法的时间复杂度为 $O(\sqrt n)$ 。

求一个数的欧拉函数值：

inline int getPhi(int n) {
    int res = n;
    for (int i = 2; i * i <= n; ++i)
        if (n % i == 0) {
            res -= res / i;
            for (; n % i == 0; n /= i);
        }
    if (n > 1) res -= res / n;
    return res;
}

如果需要求 $\varphi(1)\sim \varphi(n)​$ 的值，用上述方法逐个求的时间复杂度为 $O(n\sqrt n)​$，有没有更快的做法呢？

线性筛求欧拉函数：

inline void getPhi(int n) {
    isNotPrime[1] = 1;
    phi[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (!isNotPrime[i]) {
            prime[++cnt] = i;
            phi[i] = i - 1;
        }
        for (int j = 1; j <= cnt && i * prime[j] <= n; ++j) {
            isNotPrime[i * prime[j]] = 1;
            if (i % prime[j] == 0) {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            } else phi[i * prime[j]] = phi[i] * (prime[j] - 1);
        }
    }
}

莫比乌斯函数

定义：

莫比乌斯函数，属于 积性函数，但不是完全积性函数。常用 $\mu$ 表示，读作 miu 。

莫比乌斯函数的定义域是全体自然数 $n$ 。

若 $n = 1$，则 $\mu(1)=1$；

若 $n$ 存在大于 $1$ 的平方因子，则 $\mu(n)=0$（平方因子即 $4 , 9 , 25$ 等）；

若 $n$ 是偶数个互不相同的质数之积，则 $\mu(n)=1$；

若 $n$ 是奇数个互不相同的质数之积，则 $\mu(n)=-1$ 。

公式：

$$\mu(n)=\left\{\begin{matrix} 1& n=1\\[2ex] (-1)^m& n=p_1\times p_2 \times \cdots \times p_m = \prod\limits_{i=1}^{m}p_i(\forall p_i \neq p_j)\\[2ex] 0& others\\ \end{matrix}\right.$$

性质 & 证明：

性质 1：

若 $n , m$ 互质，则 $\mu(nm)=\mu(n) \times \mu(m)$ 。

证明：

积性函数特有性质。

性质 2：

若 $n \neq 1$，则 $n$ 所有因子的莫比乌斯函数值的和为 $0$，即

$$\sum\limits_{d\mid n}\mu(d)=\left\{\begin{matrix} 1& n=1\\[2ex] 0& n>1 \end{matrix}\right.$$

证明：

除数函数

定义：

除数函数，属于 积性函数，但不是完全积性函数。常用 $\sigma$ 表示，读作 sigma 。

$\sigma_x(n)$ 定义为 $n$ 的正约数的 $x$ 次幂之和，即

$$\sigma_x(n)=\sum\limits_{d\mid n}d^x$$

公式：

若 $p_1 , p_2 ,\ldots, p_m$ 为 $x$ 的所有质因数，$n$ 和 $x$ 都是 自然数 。

$$\begin{aligned} \sigma_x(n) &= (1 + p_1^x+p_1^{2x}+\cdots+p_1^{a_1x})\\[1ex] &\times (1 + p_2^x+p_2^{2x}+\cdots+p_2^{a_2x})\\[1ex] &\times (1 + p_3^x+p_3^{2x}+\cdots+p_3^{a_3x})\\[1ex] &\times \cdots \cdots\\[1ex] &\times (1 + p_m^x+p_m^{2x}+\cdots+p_m^{a_mx})\\[2ex] &=\prod\limits_{i=1}^{m}\sum\limits_{j=0}^{a_i}p_i^{jx}\\[2ex] &=\prod\limits_{i=1}^{m}\frac{p_i^{(a_i+1)x}-1}{p_i^x-1}\\ \end{aligned}$$

性质 & 证明：

性质 1：

特殊地，$\sigma_0(n)$ 可以表示 $n$ 的正约数个数，$\sigma_1(n)$ 可以表示 $n​$ 的正约数之和。

证明：

根据定义即能得到该结论。

性质 2：

若 $n , m​$ 互质，且 $x​$ 是自然数，则 $\sigma_x(nm)=\sigma_x(n) \times \sigma_x(m)​$ 。

证明：

积性函数特有性质。

完全积性函数