跳转至

杜教筛

解决问题

设 \(f(n)\) 是一个积性函数，

\(g(n)\) 是一个积性函数且能快速计算前缀和，

\((f\ast g)(n)\) 能快速计算前缀和。

计算 \(S(n)=\sum_{i=1}^nf(i)\)

公式

\[ g(1)\cdot{S}(n)=\sum_{i=1}^n(f\ast{g})(i)-\sum_{i=2}^ng(i)\cdot{S}(\lfloor\frac{n}{i}\rfloor) \]
推导过程
\[ \begin{gather} \text{令: }g(n)=1(n)\\ \text{则: }f\ast{g}=\mu\ast1=\epsilon\\ \end{gather} \]
\[ \begin{align} S(n)&=\sum_{i=1}^n\epsilon(i)-\sum_{i=2}^nS(\lfloor\frac{n}{i}\rfloor)\\ &=1-\sum_{i=2}^nS(\lfloor\frac{n}{i}\rfloor) \end{align} \]
\[ \begin{gather} \text{令: }g(n)=1(n)\\ \text{则: }f\ast{g}=\varphi\ast1=Id_0\\ \end{gather} \]
\[ \begin{align} S(n)&=\sum_{i=1}^nId_0(i)-\sum_{i=2}^nS(\lfloor\frac{n}{i}\rfloor)\\ &=\frac{n\cdot(n+1)}{2}-\sum_{i=2}^nS(\lfloor\frac{n}{i}\rfloor) \end{align} \]
模版

时间复杂度 \(O(n^{\frac{3}{4}})\)

代码
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
namespace DlsSieve {
    int N;
    vector<bool> vis;
    vector<int> mob, prime;
    vector<i64> phi;
    unordered_map<i64, i64> mobSums;
    unordered_map<i64, i64> phiSums;
    void init(const int N) {
        vis.resize(0);
        vis.resize(N + 1);
        phi.resize(0);
        phi.resize(N + 1);
        mob.resize(0);
        mob.resize(N + 1);
        DlsSieve::N = N;
        mob[1] = phi[1] = 1;
        for (int i = 2 ; i <= N ; i++) {
            if (!vis[i]) {
                prime.emplace_back(i);
                phi[i] = i - 1;
                mob[i] = -1;
            }
            for (auto &x : prime) {
                if (1LL * i * x > N) break;
                vis[i * x] = true;
                if (i % x == 0) {
                    phi[i * x] = phi[i] * x; 
                    mob[i * x] = 0;
                    break;
                }
                phi[i * x] = phi[i] * phi[x];
                mob[i * x] = -mob[i];
            }
        }
        for (int i = 2 ; i <= N ; i++) {
            phi[i] += phi[i - 1];
            mob[i] += mob[i - 1];
        }
    }
    i64 gSum(i64 x) {
        return x;
    }
    i64 mobSum(i64 x) {
        if (x <= N) {
            return mob[x];
        }
        if (mobSums.count(x)) {
            return mobSums[x];
        }
        i64 res = 1;
        for (i64 L = 2, R ; L <= x ; L = R + 1) {
            R = x / (x / L);
            res -= (gSum(R) - gSum(L - 1)) * mobSum(x / L);
        }
        return mobSums[x] = res / gSum(1);
    }
    i64 phiSum(i64 x) {
        if (x <= N) {
            return phi[x];
        }
        if (phiSums.count(x)) {
            return phiSums[x];
        }
        i64 res = x * (x + 1) / 2;
        for (i64 L = 2, R ; L <= x ; L = R + 1) {
            R = x / (x / L);
            res -= (gSum(R) - gSum(L - 1)) * phiSum(x / L);
        }
        return phiSums[x] = res / gSum(1);
    }
} // DlsSieve
例题

P4213 【模板】杜教筛（Sum）- 洛谷