Min_25 筛学习笔记
orz_z
·
·
个人记录
问题描述
求
\sum_{i=1}^{n}f(i) \pmod{Mod}
其中 f 是一个积性函数。
算法解决
主要思路就是将积性函数分为三个部分来求
- 当 i 是质数。
- 当 i 是合数。
-
当 i=1。
它的思想类似 DP。
#### $\text{step1}
求 g(n)=\sum\limits_{p\leq n}f(p)。
我们首先需要了解一下埃氏筛法（圈一个质数，划去它的倍数）引用。
先来考虑如何表示一个埃氏筛的状态。
那么用前 k 个质数来筛，最后没有被叉掉的数的最小质因子必然大于 p_k。
设 g(n,k) 表示 2 \sim n 中的所有质数或最小质因子大于 p_k 的数的 f 值和。
怎么转移？
考虑埃氏筛的过程，选定一个质数后，直接从它的平方开始筛。
所以当 p_k^2 > n 时，g_{n,k}=g_{n,k-1}。（p_k 指第 k 个质数）。
否则我们就一定会再叉掉一些数，减掉一部分 f 值。
\large g(n,k)=g(n,k-1)-f(p_k)\cdot \left(g(\lfloor\frac{n}{p_k}\rfloor,k-1)-g(p_k-1,k-1)\right)
这里利用了 f 是积性函数的条件。
理解：用前 $k-1$ 个质数来筛，把没筛掉的数，作为 $p_k$ 的倍数（这个倍数一定会与前 $k-1$ 个质数互质且这个倍数 $\cdot p_k < n$）来确定 $p_k$ 需要筛哪些点。
由于前 $k-1$ 个质数也是剩下的数，所以还要加上 $f(p_k) \cdot g_{p_k-1,k-1}$（也就是 $f(p_k)\cdot \sum\limits_{i=1}^{k-1}f(p_i)$，即 $p_k$ 与前 $k-1$ 个质数的组合）。
#### $\text{step2}
求 s(n)=\sum\limits_{i\leq n}f(i)。
设 s(n,k) 表示 1 \sim n 中最小质因子大于 p_k 的数的 f 值和。
那么有转移：
\large s(n,j)=g(n)-g(p_j)+\sum_{j<k \operatorname{and}p_k\leq \sqrt{n}}\sum_{1 \leq e \operatorname{and} p_k^e \leq n} f(p_k^e)\left(s\left(\lfloor\frac{n}{p_k^e}\rfloor,k\right) +[e \ne 1]\right)
意义为：分质数，合数考虑贡献。
质数的贡献我们已经搞好了，为 g(n)-g(p_j)，即 \sum\limits_{p\leq n}f(p)-\sum\limits_{i=1}^{j-1}f(p_i)。
合数的话，我们需要枚举最小质因子及其次数，即 k>j 的 p_k，再枚举次数 e。
由于是积性函数，我们直接将 f(p_k^e) 提出。
值得注意的是，形如 p^k,k>1 的数我们既没有在质数出枚举到，也没有在合数处提出 p_k^e 后枚举到，所以需要加上个 [e \ne 1]。
转移二：
设 s(n,j)=\sum_{i=1}^{n}f(i)[i 是质数或其最小质因子 \ge p_j]。
s(n,j)=s(n,j+1)+\sum_{p_{j+1} \leq \sqrt{n}}\sum_{1 \leq e \operatorname{and} p_{j+1}^{e}\leq n}f(p_{j+1}^{e})\left(s\left(\lfloor\frac{n}{p_{j+1}^{e}\rfloor},j+1\right)-g(p_{j+1}) \right)+f_{p_{j+1}^{e+1}}
这种方法虽然实际效率劣于方法一，但这种方法不仅算出了 s(n)，也顺带计算出了所有 s(\lfloor\frac{n}{x}\rfloor)，这是方法一做不到的。
\text{step3}
最后加上 f(1) 即可。
总时间复杂度约为 \mathcal O(\frac{n^{0.75}}{\log n})。
实现细节和代码
P5325 【模板】Min_25筛
定义积性函数 f(x)，且 f(p^k)=p^k(p^k-1)（p 是一个质数），求
\sum_{i=1}^n f(i)
对 10^9+7 取模。
首先，由题意有，$f(p)=p^2-p$，维护一下 $g_1=p$ 和 $g_2=p^2$ 的前缀和然后用 $\text{Min25}$ 筛即可。
细节：
* 在求 $g$ 的时候空间太大了，需要优化，因为 $g$ 都是由 $\frac{n}{k}$ 处推来的，众所周知 $\frac{n}{k}$ 的取值只有 $2\sqrt{n}$ 种情况，让 $id1_k$ 记录 $k\le\sqrt n$，$id2_k$ 记录 $\frac{n}{k} \le \sqrt n$，所以可以只枚举这 $2\sqrt n$ 种情况。
* **拆成的 $g$ 必须保证是完全积性函数，不然不可递推。**
```cpp
#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &t)
{
t = 0;
char c = getchar();
int f = 1;
while (c < '0' || c > '9')
{
if (c == '-')
f = -f;
c = getchar();
}
while (c >= '0' && c <= '9')
{
t = (t << 3) + (t << 1) + c - '0';
c = getchar();
}
t *= f;
}
template <typename T, typename... Args>
inline void read(T &t, Args &...args)
{
read(t);
read(args...);
}
template <typename T>
inline void write(T x)
{
if (x < 0)
{
x = -x;
putchar('-');
}
if (x > 9)
write(x / 10);
putchar(x % 10 + '0');
}
#define ll long long
const int _ = 2e5 + 7;
const int mod = 1e9 + 7;
bool v[_];
ll tot, p[_], n, sq, w[_], m, sum1[_], sum2[_], g1[_], g2[_], id1[_], id2[_];
// id1 id2 如文中所示 w[k] 为第 k 个需要处理的数
// 文中的 g 为 g2 - g1, g1 : f(k) = k, g2: f(k) = k ^ 2
// sum1 : 质数前缀和 ; sum2: 质数平方前缀和
void pre() // 线性筛
{
for (int i = 2; i <= sq; ++i)
{
if (!v[i])
{
p[++tot] = i;
sum1[tot] = (sum1[tot - 1] + p[tot]) % mod;
sum2[tot] = (sum2[tot - 1] + p[tot] * p[tot]) % mod;
}
for (int j = 1; p[j] * i <= sq && j <= tot; j++)
{
v[p[j] * i] = 1;
if (i % p[j] == 0)
break;
}
}
}
ll getid(ll x)
{
if (x <= sq)
return id1[x];
else
return id2[n / x];
}
ll f1(ll x) // 1 ~ x 前缀和
{
x %= mod;
return x * (x + 1) / 2 % mod;
}
ll f2(ll x) // 1 ~ x 前缀平方和
{
x %= mod;
return x * (x + 1) % mod * (2 * x % mod + 1) % mod * 166666668 % mod;
}
ll S(ll x, int j)
{
if (p[j] > x)
return 0;
ll Ans = ((g2[getid(x)] - g1[getid(x)] + mod) % mod - (sum2[j] - sum1[j] + mod) % mod + mod) % mod;
for (int i = j + 1; i <= tot && p[i] * p[i] <= x; ++i)
for (ll e = 1, sp = p[i]; sp <= x; sp *= p[i], ++e)
Ans = (Ans + sp % mod * (sp % mod - 1) % mod * (S(x / sp, i) + (e > 1)) % mod) % mod;
return Ans;
}
signed main()
{
read(n);
sq = sqrt(n);
pre();
for (ll l = 1, r; l <= n; l = r + 1)
{
r = (n / (n / l)), w[++m] = n / l;
g1[m] = f1(w[m]) - 1, g2[m] = f2(w[m]) - 1; // 处理 g(?, 0)
if (w[m] <= sq)
id1[w[m]] = m;
else
id2[n / w[m]] = m;
}
for (int i = 1; i <= tot; ++i) // dp 处理 g 函数
{
for (int j = 1; j <= m && p[i] * p[i] <= w[j]; ++j)
{
g1[j] = (g1[j] - p[i] * (g1[getid(w[j] / p[i])] - sum1[i - 1]) % mod + mod) % mod;
g2[j] = (g2[j] - p[i] * p[i] % mod * (g2[getid(w[j] / p[i])] - sum2[i - 1]) % mod + mod) % mod;
}
}
write((S(n, 0) + 1ll) % mod), putchar('\n');
return 0;
}
```
### 例题
#### [P4213 【模板】杜教筛（Sum）](https://www.luogu.com.cn/problem/P4213)
给定一个正整数 $n$，求
$$
ans1=\sum_{i=1}^{n}\varphi(i)\\
ans2=\sum_{i=1}^{n}\mu(i)
$$
先看 $\varphi$，由 $\varphi(p)=p-1$，我们可以维护 $p$ 和 $1$ 的前缀和。
另外，由 $\varphi(p^c)=p^{c-1}(p-1)$，可知，质数的整次幂的函数值也很好求。
然后是 $\mu$，显然 $\mu(p)=-1$，我们可以维护 $1$ 的前缀和，然后取反。
另外，$\mu(p^k)=0(k>1)$，因此求 $s$ 时不需要枚举最小质因子的次数。
[CODE](https://www.luogu.com.cn/paste/jc7tyj9v)
#### [loj 6235 区间素数个数](https://loj.ac/p/6235)
求 $1 \sim n$ 之间素数个数。
$2 \leq n \leq 10^{11}$。
求质数个数，联想到 $\text{Min25}$ 筛的第一步。相当于求 $f(p)=1$ 这个函数在质数处取值的前缀和。
[CODE](https://www.luogu.com.cn/paste/wi6kpie1)
#### [loj 6181 某个套路求和题](https://loj.ac/p/6181)
记
$$
f(n)=\prod_{d|n}\mu(d)
$$
求
$$
\sum_{i=1}^{n}f(i) \pmod{998244353}
$$
$1 \leq n \leq 10^{10}$。
易得
$$
ans=\sum_{i=1}^{n}\mu(i)^2-\sum_{i=1}^{n}2\times [i \in \text{primes}]
$$
套个 $\text{Min25}$ 筛即可。
[CODE](https://www.luogu.com.cn/paste/uwnqderc)
#### [loj 6053 简单的函数](https://loj.ac/p/6053)
> 求积性函数 $f(p^c)=p\oplus c,p\in \text{primes}$ 的前缀和 $\pmod{10^9+7}$。
>
> $1 \leq n \leq 10^{10}$。
易得
$$
f(p)=\begin{cases}p-1 & p \ne2 \\p+1& p=2\end{cases}
$$
我们可以先把 $f(p)$ 当成 $p-1$，然后维护 $p$ 和 $1$ 的前缀和，最后特判即可。
注意，我们应当保证拆成的若干个函数是完全积性函数。
[CODE](https://www.luogu.com.cn/paste/ir7nregx)
[SP34096 DIVCNTK - Counting Divisors (general)](https://www.luogu.com.cn/problem/SP34096)
求 $\sum\limits_{i=1}^{n}d(i^k) \pmod{2^{64}}$。
其中 $d(i)$ 表示 $i$ 的约数个数。
多测。
设 $f(x)=d(x^k)$。
则 $f$ 满足一下几条性质：
* $f(1)=1$。
* $f(p)=k+1,p\in \text{primes}$。
* $f(p^c)=kc+1$。
* $f(ab)=f(a)\times f(b),\gcd(a,b)=1$。
套个 $\text{Min25}$ 筛即可。
[CODE](https://www.luogu.com.cn/paste/3odjq9r6)
多倍经验（修改一下 $k$ 的值即可）。
[SP20173 DIVCNT2 - Counting Divisors (square)](https://www.luogu.com.cn/problem/SP20173)
[SP20174 DIVCNT3 - Counting Divisors (cube)](https://www.luogu.com.cn/problem/SP20174)
### 总结
用 $\text{Min25}$ 做题主要是要想清楚两个问题：
1. 该函数在质数处的取值怎么求和？
2. 质数的次幂处的取值 $f(p^c)$ 能否快速求？