筛法，亚线性与线性

筛法

筛法是数学中的重要部分，线性筛是很多问题的开始，而亚线性筛是很多问题的结束所以现在由易到难，逐渐归纳数学中的筛法

一、埃氏筛(埃拉托斯特尼筛法)

埃氏筛其实不是线性筛法~~所以它不配出现在这里~~，但是为了给亚线性筛打基础，还是得简单提一句：埃氏筛的思想简单易懂：从小到大考虑范围内的每一个数，然后把质数的所有倍数都标记成合数，那么最后没有被标记的数就是质数了，下面给出代码：

//n为枚举上界，vis[i] == 1表示i为合数，p[]为质数数组，tot为质数个数，下同。
void Eratosthenes(int n)
{
    vis[0] = vis[1] = 1;
    for(int i = 2;i<=n;i++)
    {
        if(!vis[i]){
            p[++tot] = i;
            if(i * i <= n)
            for(int j = i*i;j<=n;j+=i) vis[j] = 1;
            //小优化，2~i-1的倍数之前已经筛过了，直接从i的倍数开始可以加快速度
        }
    }
}

带有优化的埃氏筛的时间复杂度为 $O(n \log \log n)$

二、欧拉筛

经常说的“线性筛”也是指这个筛法，但我个人更喜欢叫它欧拉筛。

欧拉筛是质数的线性筛法，也经常用来预处理 $\varphi$ 和 $\mu$ 的值欧拉筛的特点是每个数只被自己的最小质因子筛去，因此是线性算法(所以欧拉筛在筛出合数的同时可以求出每个合数的最小质因子)。下面给出欧拉筛处理 $\varphi$ 和 $\mu$ 的代码(代码中未取模) ：

void euler(int n)
{
    mu[1] = phi[1] = 1;
    vis[0] = vis[1] = 1;
    for(int i = 2;i<=n;i++)
    {
        if(!vis[i]) {p[++tot] = i;mu[i] = -1;phi[i] = i-1;}
        for(int j = 1;j<=tot && i * p[j]<=n;j++)
        {
            vis[i * p[j]] = 1;
            if(i % p[j] == 0) {
                phi[i * p[j]] = phi[i] * p[j];
                mu[i * p[j]] = 0;
                break;
            }
            mu[i * p[j]] = -mu[i];
            phi[i * p[j]] = phi[i] * (p[j]-1);
        }
    }
}

欧拉筛预处理 $\varphi$ 和 $\mu$ 的过程完全依赖于他们的性质，他们的性质在文章数论函数总结中有过提及。

实际上欧拉筛可以在线性时间内预处理几乎所有积性函数，只是实现方式各不相同罢了。总体的思想就是表示成枚举质因子来统计贡献的形式，然后用质因子更新倍数。

三、杜教筛

参考资料：

oi-wiki Gypsophila 的博客

杜教筛是处理数论函数前缀和问题的优秀亚线性算法，码量不太大。

对于数论函数 $f$ ，我们要计算 $S(n) = \sum_{i=1}^nf(i)$

我们想办法构造一个 $S(n)$ 关于 $S( \lfloor \frac{n}{i} \rfloor )$ 的递推式。

我们发现对于任意一个数论函数 $g$ 必定满足：

\sum_{i = 1}^n(f * g)(i) = \sum_{i = 1}^n \sum_{d \mid i}g(d) f \left ( \frac{i}{d} \right ) = \sum_{i = 1} ^n g(i) S \left ( \lfloor \frac{n}{i} \rfloor \right )

证明：

$g(d) f \left (\frac{i}{d} \right )$ 是对应的一个 $i$ 的贡献，我们把这个式子的两部分分开考虑，枚举 $d,\frac{i}{d}$ （就是下文式子中的 $i,j$ ）发现这个和式就可以拆成一个二重和式：

\begin{split} &\sum_{i = 1}^n \sum_{d \mid i}g(d) f \left ( \frac{i}{d} \right )\\ =& \sum_{i = 1}^n\sum_{j = 1}^{\lfloor \frac{n}{i} \rfloor} g(i)f(j)\\ =& \sum_{i = 1}^ng(i) \sum_{j = 1}^{\lfloor \frac{n}{i} \rfloor} f(j)\\ =& \sum_{i = 1}^ng(i)S\left ( \left \lfloor \frac{n}{i} \right \rfloor \right ) \end{split}

那么就可以得到递推式：

g(1)S(n) = \sum_{i = 1}^n(f * g)(i) - \sum_{i = 2}^n g(i)S\left ( \left \lfloor \frac{n}{i} \right \rfloor \right )

那么如果我们可以寻找到一个合适的函数 $g$ ，从而能够对 $\sum_{i = 1}^n(f * g)(i)$ 快速求和，就可以使用数论分块处理后边的半个式子从而快速求出 $g(1)S(n)$ 。

思路的框架就像是这样（来自于Gypsophila巨佬的杜教筛题解） :

ll Getsum(int x) // 用这个函数来计算 f 的前缀和
{
    ll ans = f_g_sum(n);    // 计算 f * g 的前缀和
    // 以下是数论分块的部分
    for(ll l = 2,r;l <= n;l = r + 1) // l 从 2 开始
    {
        r = n / (n / l);
        ans -= (g_sum(r) - g_sum(l - 1)) * Getsum(n / l); //递归求解
        // g_sum 是 g 的前缀和
    }
    return ans;
}

这份代码的时间复杂度是 $O(n^{\frac{3}{4}})$

其中若涉及多次求解还常常把查出的结果记忆化，或者通过小数据线性筛预处理大数据记忆化的方式来达到优化时间的作用。

当使用线性筛筛出前 $n^{\frac{2}{3}}$ 个答案时，优化后的复杂度为 $O(n^{\frac{2}{3}})$

可以使用哈希表来存下已经求过的答案，也可以不用。

考虑到上面的求和过程中出现的都是 $\lfloor \frac{n}{i} \rfloor$ 。开一个大小为两倍 $\sqrt n$ 的数组 $dp$ 记录答案。如果现在需要求出 GetSum(x) ，若 $x \leq \sqrt n$ ，返回 dp[x] ，否则返回 dp[sqrt n + n / i] 即可。这样可以省去哈希表的复杂度。

杜教筛目前所见最多的应用是被用来求 $\varphi$ 和 $\mu$ 的前缀和（尤其是配合莫比乌斯反演使用），是处理数论问题的一个有力工具。

杜教筛虽然作为亚线性筛听起来很难，但是实际上它的理论知识也就只有这些。

下面我们以洛谷上的模板题 P4213 【模板】杜教筛（Sum）为例来描述一下杜教筛的实现。

题目：

给定一个正整数 $n$ ，求：

ans_1 = sum_{i = 1}^n\varphi(i)

ans_2 = sum_{i = 1}^n \mu(i)

多组数据， $1 \le T \le 10,1 \le n \le 2^{31}$

~~显然是杜教筛板子题~~

求 $\mu$ 的前缀和：显然有 $\mu \ast 1 = \varepsilon$ ，所以取 $f = \mu,g = 1,f * g = \varepsilon$ ，其中 $\varepsilon$ 的前缀和就是 $1$ ， $1$ 的前缀和就是 $n$ 。代码：

ll S_mu(ll n)
{
    if(n < N) return sum_mu[n]; // 线性筛预处理出来的内容
    if(mp_mu.count(n)) return mp_mu[n]; // 记忆化的内容
    ll res = 1; // 单位元的前缀和就是1
    for(ll l = 2,r;l<=n;l = r + 1)
    {
        r = n / (n / l);
        res -= S_mu(n / l) * (r - l + 1); // 1在l到r的和就是 r - l + 1
    }
    return mp_mu[n] = res;
}

然后我们就搞完了 $\mu$ 的部分 2. 求 $\varphi$ 的前缀和如果不考虑可以通过已经求得的 $\mu$ 的前缀和来求出 $\varphi$ （但是后边会提到），我们用同样的套路来写这一部分：考虑到 $\varphi \ast 1 = id$ ，取 $f = \varphi , g = 1,f \ast g = id$ 其中 $id$ 的前缀和是 $\frac{n \ast (n + 1)}{2}$ 那么代码就是这样：

ll S_phi(ll n)
{
    if(n < N) return sum_phi[n]; // 线性筛预处理出来的内容
    if(mp_phi.count(n)) return mp_phi[n]; // 记忆化的内容
    ll res = 1ll * n * (n + 1) / 2; // id 的前缀和
    for(ll l = 2,r;l<=n;l = r + 1)
    {
        r = n / (n / l);
        res -= S_phi(n / l) * (r - l + 1); // 1在l到r的和就是 r - l + 1
    }
    return mp_phi[n] = res; // 记忆化
}

这样我们就以同样的方式处理完了 $\varphi$ 的前缀和，其实本题做到这里就已经能过了。但是我们仔细观察“常用卷积”就会发现： $\mu \ast id = \varphi$ ，我们立即敏锐地意识到：优化的机会来了！

\begin{split} \sum_{i = 1}^n \varphi(i) &= \sum_{i = 1}^n \sum_{j = 1}^i [\gcd(i,j) = 1]\\ &= \sum_{i = 1}^n \sum_{j = 1}^i \sum_{d \mid \gcd(i,j)} \mu(d)\\ &= \sum_{d = 1}^n\mu(d)\sum_{i = 1}^n \sum_{j = 1}^i[d \mid \gcd(i,j)]\\ &= \sum_{d = 1}^n \mu(d) \sum_{i = 1}^{\left \lfloor \frac{n}{d} \right \rfloor }i\\ &= \sum_{d = 1}^n\frac{\mu(d)\left \lfloor \frac{n}{d} \right \rfloor \left (\left \lfloor \frac{n}{d} \right \rfloor + 1 \right)}{2} \end{split}

然后发现这个可以整除分块， $\mu(d)$ 的值我们前边已经求出了，所以单次求解的复杂度降到了 $O(\sqrt{n})$

到这里我们就做完了这道板子题，实际上只要能灵活运用这一部分的内容就已经足以面对大部分的场合。

然而对于一些题目则要求较详细地了解这个筛法，比如 P3768 简单的数学题，在莫比乌斯反演总结中作为例题写了题解

筛法

一、埃氏筛(埃拉托斯特尼筛法)

二、欧拉筛

三、杜教筛

四、Min_25 筛