0.积性函数

定义，若函数 $f(xy) = f(x)f(y),x \perp y$ ，则称 $f(x)$ 是积性函数。

若 $f(xy) = f(x)f(y)$ ，则称 $f(x)$ 是完全积性函数。

1.埃拉托斯特尼筛法

我们发现，大于 $1$ 的正整数 $n$ 的 $x(x \gt 1)$ 倍是合数，所以，我们可以从 $2$ 开始，标记每个没有被标记的数的倍数，剩下的就是合数。

时间复杂度 $\Omicron(n \log \log n)$ 。

可以用 bitset 优化，卡常后甚至可以 $\Omicron(n \log \log n)$ 艹 $\Omicron(n)$

1
bitset<MAXN> vis;
2
vector<int> prime;
3
inline void Sieve()
4
{
5
    vis[1] = 0;
6
    for(int i = 2;i <= n;i++)
7
    {
8
        if(!vis[i])
9
        {
10
            prime.push_back(i);
11
            int t = i;
12
            while(t <= n)
13
                vis[t] = 1,t += i;
14
        }
15
    }
16
}

2.欧拉筛法

我们发现，埃筛会重复标记一些合数，所以我们只要不重复标记合数，时间复杂度就能做到 $\Omicron(n)$ 。

因此，我们可以在 $i \bmod p = 0$ 时退出循环。因为这个时候 $i$ 是 $p$ 的倍数，被 $p$ 筛过了，所以就不用计算多次。

代码如下。

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
constexpr int MAXN = 1e8 + 5;
5
int n,q,k;
6
bitset<MAXN> vis;
7
vector<int> prime;
8
signed main()
9
{
10
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
11
    cin >> n >> q;
12
    vis[1] = 0;
13
    for(int i = 2;i <= n;i++)
14
    {
15
        if(!vis[i])
16
            prime.push_back(i);
17
        for(int& j : prime)
18
        {
19
            if(i * j > n)
20
                break;
21
            vis[i * j] = 1;
22
            if(i % j == 0)
23
                break;
24
        }
25
    }
26
}

3.欧拉筛法筛积性函数

能 $\Omicron(n)$ 前提是能 $\Omicron(1)$ 计算 $f(1),f(p),f(p ^ k)$ ，其中 $p$ 是质数。如果不能 $\Omicron(1)$ 就会在后面跟一个 $\ln T$ 。

我们首先分解 $i = \sum {p _ k} ^ {\alpha _ k}$ ，所以 $j$ 一定满足 $j \le p _ 1$ ，否则就被 $p _ 1$ 筛掉了。

若 $j \lt p _ 1$ ，则我们可以通过积性函数的定义直接得出 $f(ij) = f(i)f(j)$ 。

若 $j = p _ 1$ ，则上面就不成立了，需要记录 $low _ i$ 表示对于 $i$ 的 $p _ 1 ^ {\alpha _ 1}$ ， $\frac{i}{low _ i}$ 一定大于 $p _ i$ ，因此 $\gcd(\frac{i}{low _ i},low _ i \times j) = 1$ ，带入定义就能算出来。

如果 $low _ i = i$ ，说明 $i = p ^ k,p \text{ is prime}$ 。

代码如下：

1
bitset<MAXN> vis;
2
vector<int> prime;
3
int low[MAXN],f[MAXN];
4
inline void Sieve()
5
{
6
    vis[1] = low[1] = 1;
7
    for(int i = 2;i <= n;i++)
8
    {
9
        if(!vis[i])
10
        {
11
            low[i] = i;
12
            prime.push_back(i);
13
            f[i] = ...;
14
        }
15
        for(int& j : prime)
16
        {
17
            if(i * j > n)
18
                break;
19
            vis[i * j] = 1;
20
            if(i % j == 0)
21
            {
22
                if(low[i] = i)
23
                    f[i * j] = ...(一般由 f[i] 递推);
24
                else
25
                    f[i * j] = f[i / low[i]] * f[low[i] * j];
26
                break;
27
            }
28
            low[i * j] = j;
29
            f[i * j] = f[i] * f[j];
30
        }
31
    }
32
}

Thanks for reading!

线性筛

2025 2月 25 周二

620 字 · 5 分钟

算法学习笔记大数学照亮世界数学 OI 数论