# [模板] 杜教筛

### 引言

$$\boldsymbol{S}(n) = \sum_{i=1}^n \boldsymbol{f}(x)$$

### 杜教筛

\begin{aligned} \sum_{i=1}^n (\boldsymbol{f} * \boldsymbol{g})(i) & = \sum_{i=1}^n \sum_{xy = i}\boldsymbol{f}(x) \boldsymbol{g}(y) \\ &= \sum_{y=1}^n \boldsymbol{g}(y) \sum_{xy \leq n} \boldsymbol{f}(x) \\ &= \sum_{y=1}^n \boldsymbol{g}(y) \sum_{x=1}^{\lfloor \frac{n}{x}\rfloor} \boldsymbol{f}(x) \\ &= \sum_{y=1}^n \boldsymbol{g}(y) \boldsymbol{S}(\lfloor \frac{n}{x} \rfloor) \end{aligned}

$$\boldsymbol{g}(1) \boldsymbol{S}(n) = \sum_{i=1}^n (\boldsymbol{f} * \boldsymbol{g})(i) – \sum_{y=2}^n \boldsymbol{g}(y) \boldsymbol{S}(\lfloor \frac{n}{x} \rfloor)$$

### 求欧拉函数的前缀和

$$\boldsymbol{\varphi} * \boldsymbol{1} = \boldsymbol{id}$$

inline long long getPhi(long long n){
if(n < SIZ){
return sumA[n];
}

int x = N / n;

if(visA2[x])
return sumA2[x];

visA2[x] = true;
long long &ans = sumA2[x];

ans = n * (n + 1) / 2;

int r;
for(register int l=2; l<=n; l = r + 1){
r = n / (n / l);
ans -= (r - l + 1) * getPhi(n / l);
}

return ans;
}


### 求莫比乌斯函数的前缀和

$$\boldsymbol{\mu} * \boldsymbol{1} = \boldsymbol {\epsilon}$$

inline int getMu(int n){
if(n < SIZ)
return sumB[n];

int x = N / n;

if(visB2[x])
return sumB2[x];

visB2[x] = true;
long long &ans = sumB2[x];

ans = 1;

int r;
for(register int l=2; l<=n; l = r + 1){
r = n / (n / l);
ans -= (r - l + 1) * getMu(n / l);
}

return ans;
}