文章总览：童年

虽然但是，我们熟知的筛法应该是欧拉筛和埃式筛等筛质数的筛，属于直观意义上的“筛子”；我们也知道，欧拉筛其实是可以筛积性函数的；但是这次的两个筛不太一样，他们的作用是在于快速计算积性函数前缀和，不过他们的实现手法和思想与这些直观意义上的筛子相近，所以也被称为“筛”。

下面是本文大纲：

  1. 狄利克雷卷积的定义与性质
  2. 狄利克雷卷积的两个重要结论
  3. 常见的积性函数及其计算方式
  4. 线性筛筛积性函数的推导
  5. 线性筛常见应用二则
  6. 杜教筛的推导
  7. 杜教筛的常见应用二则
  8. Min_25 筛的推导
  9. Min_25 筛的常见应用一则

前置知识：邂逅

狄利克雷卷积基础

狄利克雷卷积的定义非常简单，就是对于两个数论函数 $f(x),g(x)$，他们狄利克雷卷积后的结果 $h(x)$ 定义为：

狄利克雷卷积的计算过程可以简单表示为 $h=f\ast g$ 然后我们就可以有如下狄利克雷卷积的性质：

  1. 交换律：$f\ast g=g\ast f$ 。
  2. 结合律：$(f\ast g)\ast h=f\ast(g\ast h)$ 。
  3. 分配律：$(f+g)\ast h=f\ast h+g\ast h$ 。
  4. 等式性质：$(f\ast h)=(g\ast h)\Longleftrightarrow f=g$ 。
  5. 单位元：$f\ast\varepsilon =f$，其中 $\varepsilon(x)=[x=1]$ 。
  6. 逆元：对于任意 $f(x)\neq 0$ 的数论函数，如果有函数 $g(x)$ 满足 $f\ast g=\varepsilon$ 则称 $g(x)$ 是 $f(x)$ 的逆元。

另外提一嘴关于狄利克雷卷积中的逆元的表达式，设有积性函数 $f(x)$，有函数 $g(x)$ 满足 $f*g=\varepsilon$，即 $g$ 为 $f$ 的逆元，我们可以有 $g(x)$ 的表达式：

这个其实非常好推，就是你把他分为 $x =1$ 和 $x>1$ 的情况然后 $x=1$ 我们有 $f(1)g(1)=1$ 即 $g(1)=\tfrac{1}{f(1)}$；对于 $x>1$ 的情况来说，我们将 $d=1$ 的子项提出来，就可以有：

但是这样两个表达式的形式不统一，这就很难受，于是说我们注意到当 $x=1$ 时如果强制代入 $x>1$ 的式子，求和部分就是 $0$ 因为 $1$ 不存在非 $1$ 的因子，但是 $x=1$ 时候的因子分子是 $1$ 这时候就注意到了重要的单位元函数 $\varepsilon$ 这与我们的初衷不谋而合，所以经过整合就得到了开始时候的式子。

就是说狄利克雷卷积和乘法有很高的相似性，上述性质在了解了狄利克雷卷积生成函数后就是非常好理解的，但是由于没有太大必要，这些定律又可以认为算是半常识级别，所以不予证明，想要了解的可以前往 狄利克雷生成函数 - OI Wiki 了解。

狄利克雷卷积结论

结论一：两个积性函数的狄利克雷卷积也是积性函数。

证明：设有积性函数 $f(x),g(x)$ 他们的狄利克雷卷积卷积设为 $h$，设下有 $(a,b)=1$ 则：

计算 $h(a)h(b)$ 的第二步的理由是首先由于 $(a,b)=1$ 可以知道他们没有任何重复的因子，所以说对于 $a,b$ 因子的 $d_1,d_2$ 显然满足条件 $(d_1,d_2)=1$，又因为 $f,g$ 都是积性函数，而他们两两互素，所以显然可以有 $f(d_1d_2)=f(d_1)f(d_2)$ 和 $g(\tfrac{ab}{d_1d_2})=g(\tfrac{a}{d_1})g(\tfrac{b}{d_2})$ 最后这些 $d_1d_2$ 可以凑出 $ab$ 所有的因子，就得出了最后 $h(ab)$ 的结果。证毕。

结论二：积性函数的逆元也是积性函数。

证明：还是逆元问题，老套路。设 $f*g=\varepsilon$，其中 $f$ 是一个积性函数，那么根据积性函数的性质，$f(1)$ 只能等于 $1$，然后我们开始用归纳法推出该定理。

  1. 若 $nm=1$，则显然代入上面的逆元计算公式有 $g(nm)=\tfrac{\varepsilon(nm)}{f(nm)}=1$ 显然满足积性函数性质。

  2. 若 $nm>1$ 且 $(n, m)=1$，假设 $\forall\ xy\lt nm$ 且 $(x,y)=1$ 都有 $g(xy)=g(x)g(y)$ 即对于所有小于 $nm$ 的参数 $xy$，函数 $g$ 都满足积性函数性质，则代入狄利克雷卷积逆元计算公式我们有（因为 $f$ 是积性函数满足 $f(1)=1$ 所以将分母舍去）：

    第二个等号的部分就是将 $d$ 拆分，和结论一中的证明类似的手法。显然的如果 $ab\neq 1$ 那么对于所有的正整数 $ab$ 都有 $\tfrac{nm}{ab}<nm$，也就是说 $g(\tfrac{nm}{ab})$ 也是满足积性函数性质的，那么我们有：

    这里标注的 $(1)$ 式就是我们本来要减去除了 $ab=1$ 以外的所有那些项，但是这样的式子我们推起来就很难受，他不满足狄利克雷卷积的形式，所以要做出一定变化，然后呢就注意到，我们要是减去了 $ab=1$ 的情况答案就减多了，不合理。所以说我们考虑把它加回来，就有了现在的 $(1)$ 式。

    对于标注的 $(2)$ 式，其实就是变化枚举顺序，这样的话拆分出单个的狄利克雷卷积形式的答案，我们就可以把常数 $\varepsilon(m)$ 从 sum 中提出来然后再化简出 $\varepsilon(n)$。最后因为 $\varepsilon$ 是积性函数且 $nm>1$ 所以这个函数的值是 $0$ 也就剩下了 $g(nm)=g(n)g(m)$。

    也就是说我们可以从所有小于 $nm$ 的 $xy$ 其中 $xy$ 满足积性函数的性质推出 $nm$ 也满足积性函数性质。

综上，积性函数的逆元也一定是积性函数。

常见积性函数计算

首先说一下积性函数的定义，对于一个函数 $f$，如果 $f(1)=1$ 且对于 $\forall ab,(a,b)=1$ 满足 $f(ab)=f(a)f(b)$ 则该函数 $f$ 被称为积性函数。特殊的，如果对于 $(a,b)\neq1$ 函数 $f$ 同样满足 $f(ab)=f(a)f(b)$ 则函数 $f$ 被称为完全积性函数。

常见积性函数：

  1. 单位函数：$\varepsilon(n)=[n=1]$。（完全积性）
  2. 恒等函数：$\operatorname{id}_k(n)=n^k$，其中 $\operatorname{id}_1(n)$ 简记为 $\operatorname{id}(n)$。（完全积性）
  3. 常数函数：$I(n)=1$。（完全积性）
  4. 除数函数：$\sigma_k(n)=\sum_{d\mid n}d^k$，其中 $\sigma_0(n)$ 简记为 $\operatorname{t}(n)$，$\sigma_1(n)$ 简记为 $\sigma(n)$。
  5. 欧拉函数：$\varphi(n)=\sum_{i=1}^{n-1}[i\perp n]$，计算公式 $\varphi(n)=n\prod_{p\mid n}(1-\tfrac{1}{p})$ ，其中 $p$ 为素数。
  6. 莫比乌斯：$\mu(n)=\begin{cases}1&n=1\\0&\exists\ d>1,d^2\mid n\\ (-1)^{\omega(n)}&\operatorname{otherwise.}\end{cases}$，$\omega(n)$ 表示 $n$ 本质不同的素因子个数。

关于积性函数的狄利克雷卷积：

  • $\varepsilon=\mu*I$
  • $t=I*I$
  • $\sigma=\operatorname{id}\,*\ I$
  • $\varphi=\mu*\operatorname{id}$
  • $\operatorname{id}=\varphi * I$

关于所谓的构造题，其实就是利用变换式子的技巧，做莫比乌斯变换啊算狄利克雷生成函数这样的反复利用数论函数的性质从而构造出合适函数再通过计算推出题目想要的结果。

算法其一：自我

线性筛推导

猛然发现以前没有说过线性筛筛积性函数，那就浅浅的来一下罢。

友情链接：

【算法介绍】素数筛法 | 祝馀宫

众所周知，正常的筛素数模板应该是长这样：

1
2
3
4
5
6
7
8
9
10
11
12
13
bool isprime[MAXN];
int prime[MAXN]; 
int n; 
int cnt;
memset(isprime, true, sizeof(isprime)); 
isprime[1] = false; 
for(int i = 2; i <= n; i++) { 
    if(isprime[i]) prime[++cnt] = i;
    for(int j = 1; j <= cnt && i * prime[j] <= n; j++) {
        isprime[i * prime[j]] = false;
        if(i % prime[j] == 0) break;
    }
}

那么显而易见的这里有几种情况：

  1. if(isprime[i]) prime[++cnt] = i; 表示一个素数
  2. isprime[i * prime[j]] = false; 我们找到了这个合数的最小素因子
  3. if(i % prime[j] == 0) break; 这个合数有了比我们当前枚举出来的素数更小的素因子

这其实就意味着积性函数的三种情况，这也意味着我们如果要用线性筛来筛出积性函数，我们必须要计算出积性函数对于这些情况的式子，我们可以将其抽象一下，设有积性函数 $f$ 则我们要算：

  1. $f(p)$
  2. $f(i\times p),\gcd(i,p)=1$
  3. $f(i\times p),p\mid i$

那其实目标就非常明确了，我们来看看接下来两个应用。

线性筛模板

我们先来最基本的，线性筛筛欧拉函数。那么显然的，对于上面的情况我们有：

  1. $\varphi(p)=p-1$
  2. $\varphi(i\times p),(i,p)=1,\varphi(ip)=\varphi(i)\times \varphi(p)$
  3. $\varphi(i\times p),p\mid i$ 我们可以从欧拉函数计算公式得出 $\varphi(i\times p)=p\times \varphi(i)$

欧拉函数计算公式是这样的：

所以我们可以有这样的代码来计算欧拉函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
vector<int> pri;
bool isp[N];
int phi[N];

inline void Init(int n) {
    phi[1] = 1;
    for(int i = 2; i <= n; i++) {
        if(!isp[i]) {
            pri.push_back(i);
            phi[i] = i - 1;
        }
        for(auto &p : pri) {
            if(i * p > n) break;
            isp[i * p] = 1;
            if(i % p == 0) {
                phi[i * p] = phi[i] * p;
            	break;
            }
            phi[i * p] = phi[i] * phi[p];
        }
    }
}

其实这个代码应该是特别好理解和形象的，而且这种积性函数的式子应该不算难推。我们可以再来看第二种常见的积性函数，莫比乌斯函数，它的计算公式是（下式中的 $\omega$ 上面说过了，懒得赘述）

那么根据上面的线性筛我们要计算：

  1. $\mu(1)=1$ 这是定义。
  2. $\mu(p)=-1$ 显然的，因为素数 $p$ 只有一个本质不同的素因子。
  3. $\forall (i,p)=1,\mu(i\times p)=\mu(i)\times\mu(p)$ 这也显然这是积性函数的定义。
  4. $\forall p\mid i,\mu(i\times p)=0$ 因为 $i$ 有一个因子 $p$ 再乘上 $p$ 以后显然会有因子 $p^2$。

所以轻而易举的得出代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
vector<int> pri;
bool isp[N];
int mu[N];

inline void Init(int n) {
    mu[1] = 1;
    for(int i = 2; i <= n; i++) {
        if(!isp[i]) {
            pri.push_back(i);
            mu[i] = -1;
        }
        for(auto &p : pri) {
            if(i * p > n) break;
            isp[i * p] = 1;
            if(i % p == 0) {
                mu[i * p] = 0;
            	break;
            }
            mu[i * p] = mu[i] * mu[p];
        }
    }
}

线性筛作为非常基础的筛积性函数的代码，必须理解+熟练掌握，毕竟是基础中的基础。

算法其二：投入

杜教筛推导

接下来就是万众瞩目的杜教筛了。杜教筛是一种快速计算积性函数前缀和的算法，其大致原理就是构造函数来转化复杂度，那么接下来就看怎么构造了。

我们首先需要一个小引理：

引理：设 $f,g$ 的狄利克雷卷积是 $h$，并用 $S(n)$ 表示 $f$ 前 $n$ 项前缀和，则对于 $g$ 必有：

证明：

我们还是顺推一发。首先对于第一步，其实就是运用狄利克雷卷积的定义：

带入到式子就可以得到。然后是从第一步到第二部的转化，这里需要用到很常用的一个变换，就是说如果 $d\mid i$ 也就是 $d$ 是 $i$ 的因子，那么 $i$ 一定可以表示成 $dk$ 的形式，也就是 $k=\lfloor\tfrac{i}{d}\rfloor$ 。显而易见的这时候枚举 $i$ 和枚举 $d$ 是等价的。所以说我们可以修改枚举顺序：

显然的第二个 $\sum$ 与 $g(d)$ 无关，可以作为常数提出，而剩下的部分 $k$ 就是一个连号，可以用 $S(n)$ 表示。

然后修改一下枚举变量的名称就可以得到最后的式子了。证毕！

有了这个小引理，我们就有一个可以从一个很唐的结论得到杜教筛：

就是这么显而易见，用两个上面的引理凑出 $g(1)S(n)$ 前一项可以用引理化简，后半项暂时无法计算。但是有人就说了，你这不是还是要算 $h$ 的前缀和，这有什么意义呢？你猜为什么要构造 $g$ 函数，这就是为了让 $f*g$ 的前缀和可以快速计算，这里就转化了复杂度。那么剩下来的半项如何处理？显然的就是用数论分块来解决。

另外不论函数 $f$ 是不是积性函数，只要有合适的函数 $g$ 满足条件，我们都可以用杜教筛求它的前缀和，因为可以看到上面杜教筛的全部推导中，我们都没有强调或使用过任何积性函数的性质，也就是说杜教筛的适用范围其实是不限制于积性函数的。

现在可以适当的考虑一下代码中关于杜教筛的细节问题，其实就是如何用代码来实现后半部分的计算。我们可以通过这里分块的形式来计算贡献。先来穷举一波，设 $n=10$ 则对答案的贡献为：

$i$ 的值 对答案的贡献
2 $g(2)S(5)$
3 $g(3)S(3)$
4 $g(4)S(2)$
5 $g(5)S(2)$
6 $g(6)S(1)$
7 $g(7)S(1)$
8 $g(8)S(1)$
9 $g(9)S(1)$
10 $g(10)S(1)$

注意到根据整除分块的结构，每一块的 $S$ 都是相同的，可以提出来，那么每一块的 $g$ 就变成每一块左右端点内的和。也就是我们有如下代码来表示一块对答案的贡献：

1
ans -= sum_g(l, r) * S(n / l);

因为每一块的 $S(\lfloor\tfrac{n}{i}\rfloor)$ 都是一样的，所以这里不妨就直接用 S(n/l) 来表示，那么问题就变成了计算数论分块每一块的 $r$ 前提是已知数据总量 $n$ 和左端点 $l$ ，不难算出 r=n/(n/l)，这样 $g$ 的部分就可以用前缀和计算了，而函数 S 就是我们杜教筛正在求的内容，所以可以递归处理，最后别忘了记忆化，不然复杂度就爆掉了。

那么可以有这样的杜教筛模板：

1
2
3
4
5
6
7
8
9
10
11
12
map<int , ll >mp;
inline ll djs(int n) {
    if(n < N) return sum[n]; // 小范围查表
    if(mp.count(n)) return mp[n]; // 记忆化搜索，n 较大所以 mp 存储
    ll ans = sum_h(1, n); // 杜教筛公式前半部分
    for(int l = 1, r; l <= n; l = r + 1) { // 枚举左端点
        r = n / (n / l);
        ans -= sum_g(l, r) * djs(n / l);
        if(r == n) break;
    }
    return mp[n] = ans; // 完结撒花
}

杜教筛模板

我们来看杜教筛的经典运用，也就是杜教筛求欧拉函数和莫比乌斯函数，来一个逐个击破，先推欧拉函数这个老朋友，根据杜教筛的公式，我们要构造 $g$ 使得 $f\ast g$ 的前缀和还有 $g$ 的前缀和可以快速计算。那么从最开始 常见积性函数计算 的内容中，我们可以得知 $\varphi\ast\operatorname{I}=\operatorname{id}$ 显而易见这些函数都是可以快速计算的，则代入上面的模板我们就有：

1
2
3
4
5
6
7
8
9
10
inline ll djsphi(int n) {
    if(n < N) return sump[n];
    if(wp.count(n)) return wp[n];
    ll ans = 1LL * n * (n + 1) / 2;
    for(int l=2, r; l<=n; l=r+1) {
        r = n / (n / l);
        ans -= (r - l + 1) * djsphi(n / l);
    }
    return wp[n] = ans;
}

而莫比乌斯函数也是一样的，我们知道 $\mu\ast\operatorname I =\varepsilon$ 则就有

1
2
3
4
5
6
7
8
9
10
inline ll djsmu(int n) {
    if(n < N) return sumu[n];
    if(wu.count(n)) return wu[n];
    ll ans = 1;
    for(int l=2, r; l<=n; l=r+1) {
        r = n / (n / l);
        ans -= (r - l + 1) * djsmu(n / l);
    }
    return wu[n] = ans;
}

关于杜教筛函数推导的方式，主要是迪利克雷生成函数和莫比乌斯反演，这个我会从例题和新开的文章里面讲一下，这篇文章主要是基础运用。

算法其三：梦想

Min_25 筛推导

接下来是 Min_25 筛时间，虽然你看上面的前置知识全都是关于杜教筛的，Min_25 筛应该很简单吧，额，确实如此，前置知识真的没有全都是基础变换，所以我觉得是比杜教筛还抽象的存在……

Upd：说实话我真的帮不太到妄图看一遍资料就想学会的人，我一开始学到的 Min_25 筛模板和 OI-wiki 上是不一样的，但是怎么都看不懂 OI-wiki 所以全程自己推了一边后，发现 OI-wiki 上的版本比我原本的版本强太多了鱼逝这一段 Min_25 筛我打算重写，如果你也看不懂的话，建议自己手动推一遍全程再看一遍。虽然第一次写的那一版可能最后并没有用上，但是为我理解 OI-wiki 上的版本打下了基础，就当是前置知识了，严格不亏。

当然你可以认为这部分是对于 OI-wiki 抽象推导的补充说明，我尽量以通俗易懂的方式讲解关于 OI-wiki 上的细节。

接下来还是一样，声明一些常用的记号以便利推导：

  1. $x/y=\lfloor\frac{x}{y}\rfloor$。
  2. $\operatorname{isprime}(n)$ 表示 $n$ 是否为质数，如果是返回 $1$ 否则为 $0$。
  3. $p_k$ 表示全体质数中第 $k$ 小的质数，特别地，令 $p_0=1$。
  4. $\operatorname{lpf}(n)$ 返回 $n$ 最小的质因子，特别的，当 $n=1$ 时，其值为 $1$。
  5. $F_{\operatorname{prime}}(n)=\sum_{2\le p\le n}f(p)$。
  6. $F_k(n)=\sum_{i=2}^n [p_k\le\operatorname{lpf}(i)]f(i)$。

另外对于 $f$ 有如下的规定：

  1. $f$ 是积性函数。
  2. $f(p)$ 是关于 $p$ 的低阶多项式。
  3. $f(p^c)$ 是可以快速计算的。

我们要求的问题依然是 $\sum_{i=1}^n f(i)$ 即积性函数 $f$ 前缀和，观察该式子，发现与 $F_k(n)$ 的定义非常的相近，联系到 $\operatorname{lpf}$ 的定义，不难发现 $F_1(n)+f(1)$ 即为答案，又因为 $f$ 是积性函数即 $f(1)=1$，则最终答案可以确定为 $F_1(n)+1$ 。

那么如果我们可以快速计算出 $F_k(n)$ 的值，答案就已经出来了，所以开始从 $F_k(n)$ 的定义出发，推导出 $F_k(n)$ 的计算方式。其实的话就是让你计算一个通项公式，通过一些已知的值推出未知的，或者说用递归的形式缩小规模，这就是推导公式的本质。

不难注意到，这个式子中让我们特别难受的就是 $\operatorname{lpf}$ 函数，这个函数定义了这个数字最小质因子的大小下限。而这也给了我们一点提示：分解质因数。如果我们能把最小质因数提取出来，这样的话我们或许就可以缩小规模了。那么面对了分解质因数的问题，有一个很现实的问题，我们不得不面对两种数质数和合数。

因为从分解质因数的角度来讲，质数只有它本身一个质因子，很干净，我们应该可以利用它去得到一些式子。注意到一开始关于 $f$ 的规定，$f(p)$ 是关于 $p$ 的低阶多项式，也就是说如果函数 $f$ 的参数是一个质数，它一定是一个必不可少的特性，我们有必要保留，所以第一步我们要把 $F_k(n)$ 中的质数分离出来。

那么左边那一坨被分离出来的，就是合数部分，又臭又长，显然的这样并没有缩小我们问题的规模，你依然是要面对一个 $2\sim n$ 的 sum 所以肯定不是最后要的结果。那么缩小规模，对于这里的 $F_k(n)$ 来讲，其实就是这个函数增大 $k$ 与缩小 $n$，那么对于这两个我们有没有头绪呢？

我们知道，这里规定了最小质因子的大小，但是没规定次数，比如说对于 $6=2\times 3$ 我们如果把 $2$ 给除掉，现在就只剩下 $3$ 了，$3$ 的最小质因子就变成 $3$ 我们就可以增大 $k$ 的大小；而显然的如果你把一圈数的最小质因子抹掉，比如说对于 $2\sim n$ 我们把所有含有因子 $2$ 的全部除掉一个 $2$，相当于区间所有元素都除二取下底，这样也缩小了 $n$，一箭双雕。缩小问题规模的目标轻而易举的实现了。

这个东西的话，详细解释一下每一个部分吧。第一个 sum 的限制条件是 $k\le i,p_i^2\le n$ 。这是什么意思，第一个很好理解，因为最小质因子需要大于等于 $p_k$ 所以我们选择的 $p_i$ 一定满足 $i\ge k$ 。然后是第二个，这个也是显然的，如果 $p_i^2>n$ 就说明 $n$ 应该是可以表示为 $p_i$ 乘上一个比 $p_i$ 小的因子，也就是说 $p_i$ 不会再是最小质因子了，所以会出现这条限制。

第二个 sum，可能会有的一个疑问是，$c$ 为什么可以取到 $c=1$ 的值？不是说质数也就是 $p_i$ 的一次幂已经被提取出去了嘛？确实被提取出去了，但是我们不能保证合数会存在一次幂质数因子的存在，还是举例 $6=2\times 3$ 它的两个因子都是质数的一次幂。第二点要求了 $p_i^c\le n$，这个更加显然，因为 $p_i^c$ 要从 $2\sim n$ 的数字中提取出来，非常显然的是，如果 $p_i^c$ 比这些数字中最大的 $n$ 还要大，那么肯定是没有意义的。

然后呢就是这两个 sum 所包含的部分了。为什么我们可以做到把 $f(p_i^c)$ 提取出来，这是因为 $f$ 是一个积性函数，如果我们把一个数 $a$ 的某一个质因子全部提取出来，就一定会有这个提取后的数与提取出来的数互素，则一定满足积性函数的性质。提取剩下的部分，因为剩下的部分已经没有小于 $p_i$ 和等于 $p_i$ 的部分了，所以说会有 $F_{i+1}$ 的存在，关于括号里 $n/p_i^c$ 这个已经在最上面阐述化简思路的时候提到过了原因，不再赘述。

还有遗留下来的一个判定式 $[c>1]$。为什么需要这个？因为说如果我们有 $c>1$ 且 $p_i^c\le n$ 则说明这些数中一定有一个 $p_i^c$，这个数是一个合数，因为它有多个因子 $p$ 。但是，这个数提走了所有的因子 $p$ 以后，变成了 $1$，参照 $F_k(n)$ 一开始的模样，我们可以很显然的发现，它并不会处理数字 $1$，这代表着 $p_i^c$ 被我们遗忘了，所以最后要加回来。为什么限制了 $c>1$，就是因为如果 $c=1$ 的话，他就是质数本身，但是质数已经被我提取出来了，所以不用管他。

然后我们开始致力于进一步分解上式。显而易见的是，质数部分的那一块 sum，会在计算 $F_k(n)$ 的过程中被反复调用，也就是说如果我们不预处理它，会对复杂度造成非常大的压力。鱼逝接下来的化简，一定是需要处理这一坨求和式子的。第二，合数部分虽然已经可以计算，但是显然判定式子的存在使我们非常难受，所以合数部分也是我们接下来致力于分解的部分。

首先我们还是简单的下手，先来优化质数部分，反复查询连续质数前缀和，这个非常显然在诱导我们使用一个经常用到的利器——前缀和。没错，这个就是前缀和。联系到一开始的定义 $F_{\operatorname{prime}}$ 应该知道是干什么用的了吧？所以质数部分就可以可以简单的化简为：

然后来看棘手一点的合数部分，为什么说这里棘手呢？是因为其实这样的化简以后代码可以写了，不过有点繁琐，这里经行一个小优化，就是为了省略去那个烦人的 $[c>1]$。还是一样的，考虑贡献。如果我们将这个式子拆开来经行乘法分配律，那么式子中的两个部分依次会造成什么贡献呢？

似乎真的无法整合，难道这里真的就这样了？不是，我们可以很显然的得知，第一项的 $\min$ 保证正确，第二项的所有信息保证正确。但是这里的第二项的 $\max$ 真的如此吗？如果我们能证明当 $c=\lfloor\log_{p_i}n\rfloor$ 时，$F_{i+1}(n/p_i^c)=0$ 那么就可以顺理成章的得到上下两项造成的贡献相等，这样就可以拆分了。

那么审视一下条件，我们目前已知的是，$p_i^c\le n<p_i^{c+1}$，那么显然的，$n/p_i^c<p_i<p_{i+1}$，$n$ 就连下一次递归中最小的质数都碰不到，这怎么还能取到值呢？也就是说当 $c=\lfloor\log_{p_i}n\rfloor$ 时，一定有 $F_{i+1}(n/p_i^c)=0$ 证毕。

也就是说实际上这两项的生效范围是一样长的，而第二项也就是带有判定式的那一项刚好比第一项多一！我们就可以有化简后的下式：

这样的话，我们就彻底完成了关于答案函数 $F_k(n)$ 的计算，但是现在引入了新的函数 $F_{\operatorname{prime}}$ 需要计算，那么接下来就需要推导这个式子了。


接下来到了计算 $F_{\operatorname{prime}}(n)$ 的时候，我们首先还是考虑贡献，观察到计算 $F_k(n)$ 的时候，一定是存在这个质数因子才会递归，也就是说 $F_{\operatorname{prime}}(n)$ 只会在 $n$ 的因子上取值，也就是说不同的取值点就是 $1,2,\dots,\sqrt n,n/\sqrt n,\dots,n/2,n$ 一共也就是 $O(\sqrt n)$ 个取值点。

第二点，我们把质数部分提取出来的初衷，就是利用 $f(p)$ 是关于 $p$ 的低阶多项式的性质。如果我们把这个低阶多项式表示出来的话，应该是这样的形式：

这时候我们可以把每一个单项式拆出来，然后组合回去。这就是拆分的基本思路，我们可以设置一个新的函数 $g$ 显然的这个 $g$ 满足 $g(p)=p^s$，这个 $s$ 取决于我们正在计算第几次项。显然的我们只用到 $g$ 在质数上的取值，所以 $g$ 其他的值与 $f$ 本体相不相等就不关我们事了。

于是设 $G_{k}(n) := \sum_{i = 2}^{n} \left[p_{k} < \operatorname{lpf}(i) \lor \operatorname{isprime}(i)\right] g(i)$ ，即埃筛第 $k$ 轮筛完后剩下的数的 $g$ 值之和。
对于一个合数 $x \le n$ ，必定有 $\operatorname{lpf}(x) \le \sqrt{x} \le \sqrt{n}$。设 $p_{\ell(n)}$ 为不大于 $\sqrt{n}$ 的最大质数，则 $F_{\mathrm{prime}}(n) = G_{\ell(n)}(n)$，即在埃筛进行 $\ell$ 轮之后剩下的均为质数，这也是一开始说 $f$ 只在 $O(\sqrt n)$ 个取值点的原因。 考虑 $G$ 的边界值，显然为 $G_{0}(n) = \sum_{i = 2}^{n} g(i)$。（一开始特别约定了 $p_{0} = 1$ 的作用就体现出来了)
对于转移，考虑埃筛的过程，分开讨论每部分的贡献，有：

  1. 对于 $n < p_{k}^{2}$ 的部分，$G$ 值不变，即 $G_{k}(n) = G_{k - 1}(n)$。
  2. 对于 $p_{k}^{2} \le n$ 的部分，被筛掉的数必有质因子 $p_{k}$，即 $-g(p_{k}) G_{k - 1}(n / p_{k})$。
  3. 对于第二部分，由于 $p_{k}^{2} \le n \iff p_{k} \le n / p_{k}$，满足 $\operatorname{lpf}(i) < p_{k}$ 的 $i$ 会被额外减去。这部分应当加回来，即 $g(p_{k}) G_{k - 1}(p_{k - 1})$。

则有：

这样的就是 Min_25 筛的全部推导了。

Min_25 筛模板

题目大意，给定函数 $f(n)$：

显然的如果 $f(p)$ 也就是参数是一个质数的一次项，它的结果就是 $p\operatorname{xor} 1$ 如果 $p$ 是一个奇数，那么异或 $1$ 的结果就是 $f(p)=p-1$ 但是如果 $p$ 是偶数也就是说 $p=2$，最后的结果应该是 $f(2)=2+1$，于是在这里增添一个判定式，这样对于 $f(p)$ 就可以表示为 $f(p)=p-1+2[p=2]$。

另外这里也发现 $f(p^c)$ 可以快速计算而且 $f$ 事积性函数，这样的话，就是显然的 Min_25 筛了。下面的代码来自 OI-wiki 因为码风优良并且可以充分体现上述函数之间的关系，所以直接挪过来了。

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
/* 「LOJ #6053」简单的函数 */
#include <cmath>
#include <iostream>

constexpr int MAXS = 200000;  // 2sqrt(n)
constexpr int mod = 1000000007;

template <typename x_t, typename y_t>
void inc(x_t &x, const y_t &y) {
  x += y;
  (mod <= x) && (x -= mod);
}

template <typename x_t, typename y_t>
void dec(x_t &x, const y_t &y) {
  x -= y;
  (x < 0) && (x += mod);
}

template <typename x_t, typename y_t>
int sum(const x_t &x, const y_t &y) {
  return x + y < mod ? x + y : (x + y - mod);
}

template <typename x_t, typename y_t>
int sub(const x_t &x, const y_t &y) {
  return x < y ? x - y + mod : (x - y);
}

template <typename _Tp>
int div2(const _Tp &x) {
  return ((x & 1) ? x + mod : x) >> 1;
}

// 以上目的均为防负数和取模
template <typename _Tp>
long long sqrll(const _Tp &x) {  // 平方函数
  return (long long)x * x;
}

int pri[MAXS / 7], lpf[MAXS + 1], spri[MAXS + 1], pcnt;

void sieve(const int &n) {
  for (int i = 2; i <= n; ++i) {
    if (lpf[i] == 0) {  // 记录质数
      lpf[i] = ++pcnt;
      pri[lpf[i]] = i;
      spri[pcnt] = sum(spri[pcnt - 1], i);  // 前缀和
    }
    for (int j = 1, v; j <= lpf[i] && (v = i * pri[j]) <= n; ++j) lpf[v] = j;
  }
}

long long global_n;
int lim;
int le[MAXS + 1],  // x <= \sqrt{n}
    ge[MAXS + 1];  // x > \sqrt{n}
#define idx(v) (v <= lim ? le[v] : ge[global_n / v])

int G[MAXS + 1][2], Fprime[MAXS + 1];
long long lis[MAXS + 1];
int cnt;

void init(const long long &n) {
  for (long long i = 1, j, v; i <= n; i = n / j + 1) {
    j = n / i;
    v = j % mod;
    lis[++cnt] = j;
    (j <= lim ? le[j] : ge[global_n / j]) = cnt;
    G[cnt][0] = sub(v, 1ll);
    G[cnt][1] = div2((long long)(v + 2ll) * (v - 1ll) % mod);
  }
}

void calcFprime() {
  for (int k = 1; k <= pcnt; ++k) {
    const int p = pri[k];
    const long long sqrp = sqrll(p);
    for (int i = 1; lis[i] >= sqrp; ++i) {
      const long long v = lis[i] / p;
      const int id = idx(v);
      dec(G[i][0], sub(G[id][0], k - 1));
      dec(G[i][1], (long long)p * sub(G[id][1], spri[k - 1]) % mod);
    }
  }
  /* F_prime = G_1 - G_0 */
  for (int i = 1; i <= cnt; ++i) Fprime[i] = sub(G[i][1], G[i][0]);
}

int f_p(const int &p, const int &c) {
  /* f(p^{c}) = p xor c */
  return p ^ c;
}

int F(const int &k, const long long &n) {
  if (n < pri[k] || n <= 1) return 0;
  const int id = idx(n);
  long long ans = Fprime[id] - (spri[k - 1] - (k - 1));
  if (k == 1) ans += 2;
  for (int i = k; i <= pcnt && sqrll(pri[i]) <= n; ++i) {
    long long pw = pri[i], pw2 = sqrll(pw);
    for (int c = 1; pw2 <= n; ++c, pw = pw2, pw2 *= pri[i])
      ans +=
          ((long long)f_p(pri[i], c) * F(i + 1, n / pw) + f_p(pri[i], c + 1)) %
          mod;
  }
  return ans % mod;
}

using std::cin;
using std::cout;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> global_n;
  lim = sqrt(global_n);  // 上限

  sieve(lim + 1000);  // 预处理
  init(global_n);
  calcFprime();
  cout << (F(1, global_n) + 1ll + mod) % mod << '\n';

  return 0;
}

算法实战：开拓！

查看相关算法标签喵！

参考资料（以下排名不分先后）