【学习笔记】线性筛积性函数

· · 算法·理论

0. 前言

积性函数是数论中一种极其重要的函数。它是指对于一个函数 f(x)，如果 \gcd(x, y) = 1，则 f(xy) = f(x)f(y)，则 f(x) 就是一个积性函数。

积性函数大多数可以用线性筛质数的方法筛出来，本文将介绍几种常见的积性函数的筛法及一些拓展。

1. 线性筛质数

大佬可跳过这一部分内容。

如果我们要判断一个数 n 是不是质数，那么很朴素的想法就是 \Theta(\sqrt n) 的复杂度找 2 \sim \sqrt n 中有没有 n 的约数。

这是对于单独求一个数来说最优的解法。但如果有若干个数，你要求每个数是不是质数，\Theta(n\sqrt n) 那就显得有些慢了。所以伟大的数学家埃拉托斯特尼发明了一种 \Theta(n\ln \ln n) 的筛法——埃氏筛法。

很显然的是，两个大于 1 的整数的乘积一定不是质数。埃氏筛法就是根据这一点筛质数的。

首先枚举外层循环的一个数 i，然后把 i 的倍数全部筛掉，这样枚举完所有的 i 后，剩下的数就一定都是质数了。

按照这样的思路，可以写出下面的代码：

int p[N], cnt;
bool st[N];

void prime(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) p[ ++ cnt] = i;
        for (int j = 2; i * j <= n; j ++ )
            st[i * j] = true;
    }
}

你可能会说，这算法时间复杂度不是 \Theta (n \log n) 吗，怎么就是 \Theta(n\ln \ln n) 了？

没错，这份代码并不是理想的 \Theta(n\ln \ln n)，我们要对其进行优化。

容易发现的是，对于一个数 x，如果它有小于 x 的某个质因子，那么它一定是合数。

所以我们可以不用对于每一个数 i 都去寻找它的倍数，只需要找所有质数的倍数即可。

int p[N], cnt;
bool st[N];

void prime(int n)
{
    for (int i = 2; i <= n; i ++ )
        if (!st[i])
        {
            p[ ++ cnt] = i;
            for (int j = 2; i * j <= n; j ++ )
                st[i * j] = true;
        }
}

*其实在这份代码的内层循环中，j 的初始值可以赋成 i，这样也算是一个小优化。但效果微乎其微，且与本文主旨不符，遂不作说明。

这样代码的时间复杂度就是 \Theta(n\ln \ln n) 了。具体的为什么是这个值去问数学老师吧。

但是，这就结束了吗？不是说要线性筛质数吗？接下来就是伟大的数学家欧拉创造的线性筛质数。

例题 P3383 【模板】线性筛素数

容易发现，对于上面的埃筛，一个数可能会被筛掉多次。比如 12 会被 2 筛掉，又会被 3 筛掉，这样的重复操作会使时间复杂度带上一个 \ln\ln n。

怎么优化这一点呢？我们只需要让每个数只被它的最小质因子筛掉就行了。

先放出代码，再进行解释。

int p[N], cnt;      // p[i] 表示第 i 个质数
bool st[N];     // st[i] 表示 i 是否是质数

void prime(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) p[ ++ cnt] = i;
        for (int j = 1; p[j] <= n / i; j ++ )
        {
            st[i * p[j]] = true;
            if (i % p[j] == 0) break;
        }
    }
}

如果 i 之前被 p_j 筛过了，又由于 p 里面质数是从小到大的，所以 i 乘上其他的质数的结果一定会被 p_j 的倍数筛掉，就不需要在这里先筛一次，所以这里直接 break。

这样时间复杂度就变成了 \Theta(n)。

以上内容异常重要，是接下来筛其它积性函数的基础。

2. 线性筛欧拉函数

一句介绍：\varphi(x) = \sum\limits_{k = 1}^x[\gcd(k, x) = 1]，表示 1 \sim x 中与 x 互质的数。

一句求解：\varphi(n) = n \times \prod\limits_{p \mid n, p\ is\ a\ prime} \dfrac {p-1}p。

现在讨论怎么在线性筛质数把欧拉函数也求出来。

int p[N];       // p[i] 表示第 i 个质数
bool st[N];     // st[i] 表示 i 是否是质数
int phi[N];     // phi[i] 表示 φ(i) 的值
int cnt;

void prime(int n)
{
    phi[1] = 1;
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) p[ ++ cnt] = i, phi[i] = i - 1;
        for (int j = 1; p[j] <= n / i; j ++ )
        {
            st[p[j] * i] = 1;
            if (i % p[j]) phi[i * p[j]] = phi[i] * p[j];        // p[j] 不是 i 的最小质因子 
            else    // p[j] 是 i 的最小质因子 
            {
                phi[i * p[j]] = phi[i] * (p[j] - 1);
                break;
            }
        }
    }
}

3. 线性筛莫比乌斯函数

一句介绍：\mu(n) = \left\{\begin{matrix}1 & n = 1\\ 0 & n 含有平方因子\\ (-1)^{本质不同质因子个数} & \mathrm{otherwise} \end{matrix}\right.

一句求解：按照定义查找 n 的质因子个数。

现在讨论怎么在线性筛质数把莫比乌斯函数也求出来。

int p[N];       // p[i] 表示第 i 个质数
bool st[N];     // st[i] 表示 i 是否是质数
int mu[N];      // mu[i] 表示 μ(i) 的值
int cnt;

void prime(int n)
{
    mu[1] = 1;
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) p[ ++ cnt] = i, mu[i] = -1;
        for (int j = 1; p[j] <= n / i; j ++ )
        {
            st[p[j] * i] = 1;
            if (i % p[j]) mu[p[j] * i] = -mu[i];        // p[j] 不是 i 的最小质因子 
            else    // p[j] 是 i 的最小质因子 
            {
                mu[i * p[j]] = 0;
                break;
            }
        }
    }
}

4. 线性筛约数个数

一句介绍：\sigma_0(n) 表示 n 的约数个数。

一句求解：若 n = \prod\limits_{i=1}^mp_i^{c_i}，那么根据乘法原理，有 \sigma_0(n) = \prod\limits_{i=1}^m(c_i+1)。

现在讨论怎么在线性筛质数把约数个数也求出来。

在线性筛约数个数时还需要额外记录一个 num_i 数组，表示 i 的最小质因子的出现次数。

int p[N];       // p[i] 表示第 i 个质数
bool st[N];     // st[i] 表示 i 是否是质数
int d[N];       // d[i] 表示 i 的约数个数
int num[N];     // num[i] 表示 i 的最小质因子出现次数 
int cnt;

void prime(int n)
{
    d[1] = 1;
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) p[ ++ cnt] = i, d[i] = 2, num[i] = 1;
        for (int j = 1; p[j] <= n / i; j ++ )
        {
            st[p[j] * i] = 1;
            if (i % p[j]) num[i * p[j]] = 1, d[i * p[j]] = d[i] * 2;        // p[j] 不是 i 的最小质因子 
            else    // p[j] 是 i 的最小质因子 
            {
                num[i * p[j]] = num[i] + 1, d[i * p[j]] = d[i] / （num[i * p[j]] + 1) * (num[i * p[j]] + 2);
                break;
            }
        }
    }
}

5. 线性筛约数和

一句介绍：\sigma_1(n) 表示 n 的约数和。

一句求解：若 n = \prod\limits_{i=1}^mp_i^{c_i}，有 \sigma_1(n) = \prod\limits_{i=1}^m\sum\limits_{j=0}^{c_i}p_i^j。

现在讨论怎么在线性筛质数把约数和也求出来。

在线性筛约数个数时也需要额外记录一个 num_i 数组，表示 i 的最小质因子的贡献和（若 i 的最小质因子是 p_1，共出现了 c_1 次，那么 num_i = \sum\limits_{j=0}^{c_1}p_1^j）。

int p[N];       // p[i] 表示第 i 个质数
bool st[N];     // st[i] 表示 i 是否是质数
int d[N];       // d[i] 表示 i 的约数和
int num[N];     // num[i] 表示 i 的最小质因子的贡献和

void prime(int n)
{
    d[1] = 1;
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) p[ ++ cnt] = i, d[i] = num[i] = i + 1;
        for (int j = 1; p[j] <= n / i; j ++ )
        {
            st[p[j] * i] = true;
            if (i % p[j]) d[p[j] * i] = d[i] * (p[j] + 1);  // p[j] 不是 i 的最小质因子 
            else    // p[j] 是 i 的最小质因子 
            {
                d[p[j] * i] = d[i] / num[i] * (num[i] * p[j] + 1);
                num[p[j] * i] = num[i] * p[j] + 1;
                break;
            }
        }
    }
}

6. 总结及参考文献

在数论中，积性函数几乎无处不在。熟练掌握它们的求解过程乃重中之重。

参考文献：

  1. OI - Wiki : https://oi-wiki.org/math/number-theory/sieve/；
  2. 线性筛求约数个数以及约数和 : https://blog.csdn.net/calculate23/article/details/89513721；
  3. 一些积性函数 : https://blog.csdn.net/weixin_30244889/article/details/95661524；
  4. ChatGPT。

完。