RenaMoe's Blog

念念不忘，必有回响

0%

板子 欧拉线性筛

发表于 更新于 分类于 ， Valine：

欧拉线性筛可以 \(O(n)\) 筛出质数和积性函数。

筛质数

未访问的是质数

之后从质数表开始

把\(i*pri[j]\)标为访问过

如果\(i\)是\(pri[j]\)的倍数就跳出

1
2
3
4
5
6
7
8
9
10
11
vector<int> pri;
bool vis[N];
for (int i = 2; i <= n; ++i) {
    if (!vis[i])
        pri.push_back(i);
    for (int j = 0; j < pri.size() && pri[j] * i <= n; ++j) {
        vis[pri[j]*i] = true;
        if (i % pri[j] == 0)
        	break;
    }
}

筛\(\varphi(x)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
for (int i = 2; i <= n; ++i) {
    if (!tag[i])
        pri[++tot] = i, phi[i] = i - 1;
    for (int j = 1, k; j <= tot && (k = pri[j] * i) <= n; ++j) {
        tag[k] = true;
        if (i % pri[j])
            phi[k] = phi[i] * phi[pri[j]];
        else {
            phi[k] = phi[i] * pri[j];
            break;
        }
    }
}

筛\(d(x)\)

粘过来的线性筛 \(d(x)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vis[i] = d[1] = 1;
for (int i = 2; i <= n; ++i) {
    if (!vis[i]) 
        pri.push_back(i), d[i] = 2, a[i] = 1;
    for (int j = 0; j < pri.size() && i * pri[j] <= n; ++j) {
        vis[i*pri[j]] = 1;
        if (i % pri[j]) 
            d[i*pri[j]] = d[i] * d[pri[j]], a[i*pri[j]] = 1;
        else {
            d[i*pri[j]] = d[i] / (a[i] + 1) * (a[i] + 2);
            a[i*pri[j]] = a[i]+1;
            break;
        }
    }
}