杜教筛用来求数论函数前缀和。复杂度为

前提

如果我们要求，那么需要找到一个数论函数，满足的前缀和可以非常快速的求出来，并且的前缀和可以非常快速的求出来。

推导

既然的前缀和可以非常快速的求出来，我们就求的前缀和。

即。

然后我们想得到的是。所以我们让上面的式子减去一个。

对于后面这个式子,我们用来代替，就变成了

因为的前缀和可以快速求出，所以直接数论分块，后面的直接递归就好了。

这样我们得到的是，所以答案除以（一般为1）就好了。

例子

以求的前缀和为例。因为，和的前缀和都非常好求，所以我们令为即可。

再来推一下的前缀和。因为，和的前缀和都非常好求，所以还是令

关于预处理

这样直接搜的复杂度是，为了使复杂度更优，我们需要先预处理出一部分答案，如果我们预处理除了的答案，当计算中的结果时，直接返回即可。

可以证明当取时，复杂度最优秀为

关于记忆化

为了让复杂度是正确的，我们肯定要将每次算出的结果记忆化下来。因为比较大，所以需要用来记忆化。这样复杂度就会多个

还有一种方法，因为我们每次递归到的肯定满足:所有满足的中，只有会被计算到。所以我们可以用一个数组ma记忆化，当查询的小于等于时，我们直接范围答案，当查询的大于时，我们查看中的值即可。

当有多次询问时，第二种方法需要清空，复杂度可能不如第一种。

代码

以求的前缀和为例。

void pre() {
    phi[1] = 1;
    for(int i = 2;i < N;++i) {
        if(!vis[i]) {
            prime[++tot] = i;
            phi[i] = i - 1;
        }
        for(int j = 1;j <= tot && prime[j] * i < N;++j) {
            vis[prime[j] * i] = 1;
            if(i % prime[j]) {
                phi[i * prime[j]] = phi[i] * (prime[j] - 1);
            }
            else {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
        }
    }
    for(int i = 2;i < N;++i) phi[i] = (phi[i] + phi[i - 1]) % mod;
}
ll MAX;

ll PHI(ll n) {
    if(n < N) return phi[n];

    if(vis[MAX / n]) return maphi[MAX / n];
    vis[MAX / n] = 1;
    ll ret = (n % mod) * ((n + 1) % mod) % mod * inv % mod;

    for(ll l = 2,r;l <= n;l = r + 1) {
        r = n / (n / l);
        ret -= ((r - l + 1) % mod) * PHI(n / l) % mod;
        ret %= mod;
    }
    return maphi[MAX / n] = ret;
}