Min_25筛 学习小记
Rorschachindark
·
·
题解
前言
为什么叫学习小记呢？因为暂时除了模板题就几乎没有做什么东西了。（雾
这个东西折磨了我一整天，看得我身不如死，只好结合代码理解题解，差点死在机房。（话说半天综合半天竞赛真是害人不浅）
为了以后忘了再受荼毒，这里还是写一下，如果有人会看到的话，希望可以帮助到吧。（话说这个东西我已经拖了好久了啊！！！）
（话说我怎么这么多话说啊？！！）
Min_25 筛
这个东西是由聚聚\texttt{Min-25}发明了，所以我们称之为\texttt{Min-25}筛。（感觉有点民科了）那就不废话了，进入正言了。
下面的\mathbb{P}指的是质数集合，\mathbb{P_i}指的是第i个质数，其中第0个质数为0。一个最小质因数可能等于它本身。
我们考虑对于一个积性函数求和，我们可能会想到杜教筛或者洲阁筛（尽管我不是很会洲阁筛），但是两种筛法并不是很具有普遍性，特别是杜教筛。
我们考虑一个具体问题，我们现在设一个积性函数f(p^k)=p^k(p^k-1)，其中p为质数。我们需要求出\sum_{i=1}^{n} f(i)。
我们发现对于这个问题我们可以分成两个部分进行考虑，一部分为质数，另一部分为合数，所以即为:
\sum_{i=1}^{n} f(i)=\sum_{p\in\mathbb{P}\wedge 2\le p\le n} f(p)+\sum_{p\in \mathbb{P}\wedge p^e\le n\wedge p\le \sqrt n} f(p^e)(\sum_{1\le i\le n\wedge \texttt{LPF(i)}> p} f(i)+[e>1])
其中\texttt{LPF(i)}表示i的最小质因子（\texttt{Lowest Prime Factor}）。
这个式子很好理解，可能稍微难一点的就是为什么p\le \sqrt n，这是因为\texttt{LPF(n)}\le \sqrt n,s.t. n\notin \mathbb{P}。
我们发现这个式子似乎不好继续往下面搞了。
于是，我们构造一种函数g(n,i)（鬼知道这是怎么想到的），定义为:
g(n,i)=\sum_{x=1}^{n} [x\in \mathbb{P}\vee \texttt{LPF(x)}>\mathbb{P_i}]x^k
我们考虑如何求出$g(n,i)$，我们不难得出转移式:
$$g(n,i)=\left\{\begin{array}{l}
g(n,i-1) (\mathbb{P_i}^2>n)\\
g(n,i-1)-\mathbb{P_i}^k(g(\lfloor\frac{n}{\mathbb{P_i}}\rfloor,i-1)-g(\mathbb{P_{i-1}},i-1))
\end{array}\right.$$
这里还是稍微解释一下吧。很显然的是，我们的$g(n,i)$一定是$g(n,i-1)$减去最小质因数恰好为$\mathbb{P_i}$的数的贡献，而$x^k$又是完全积性函数，所以可以提出一个$\mathbb{P_i}^k$出来。又因为$\mathbb{P_i}$是最小质因数，所以能产生贡献的数除了$\mathbb{P_i}$的最小质因数一定不比$\mathbb{P_i}$小。
需要提醒的是，后文里面的$g$其实是把单项式又重新组合成多项式的，如果不是很理解可以见代码。
我们发现，我们如果设:
$$S(n,i)=\sum_{x=1}^{n} [\texttt{LPF(x)}>\mathbb{P_i}]f(x)$$
我们就可以在$S$和$g$之间连接起某种关系，即:
$$S(n,i)=g(n,|\mathbb{P}|)-\sum_{x=1}^{i} f(\mathbb{P_x})+\sum_{\mathbb{P_k}^x\le n\wedge k>i}f(\mathbb{P_k}^x)(S(\lfloor\frac{n}{\mathbb{P_k}^x}\rfloor,k)+[x>1])$$
$|\mathbb{P}|$就是平方小于等于$n$的质数的个数，意思就是小于等于$n$的质数的$f$之和，又因为要最小质因数大于$\mathbb{P_i}$，所以减去$\sum_{x=1}^{i-1} f(\mathbb{P_x})$。后面那一部分的解释跟上个部分差不多，只是需要注意最小质因数要大于$\mathbb{P_i}$。
最后的答案显然就是$S(n,0)$。
这里还有一些细节需要提，我们发现这里面函数所有的自变量都可以表示成$\lfloor\frac{n}{x}\rfloor$，于是我们其实需要的数只有$\sqrt n$个。我们直接离散化一下就好了，空间其实是可以用根号分治做到$\Theta(\sqrt n)$的。具体见代码。
# 模板题代码
```cpp
#include <bits/stdc++.h>
using namespace std;
#define Int register int
#define mod 1000000007
#define ll long long
#define MAXN 200005
int mul (int x,int y){return 1ll * x * y % mod;}
int dec (int x,int y){return x >= y ? x - y : x + mod - y;}
int add (int x,int y){return x + y >= mod ? x + y - mod : x + y;}
ll n,sw,w[MAXN];
int sq,cnt,g1[MAXN],g2[MAXN],id1[MAXN],id2[MAXN],gp1[MAXN],gp2[MAXN],pri[MAXN],vis[MAXN];
int S (ll x,int y){
if (pri[y] >= x) return 0;
int p = x <= sq ? id1[x] : id2[n / x],ret = dec (dec (g2[p],g1[p]),dec (gp2[y],gp1[y]));
for (Int i = y + 1;i <= cnt && 1ll * pri[i] * pri[i] <= x;++ i){
ll pk = pri[i];
for (Int k = 1;pk <= x;++ k,pk *= pri[i]){
int o = pk % mod;ret = add (ret,mul (o,mul (o - 1,S (x / pk,i) + (k != 1))));
}
}
return ret;
}
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');}
signed main(){
read (n);sq = sqrt (n);
for (Int i = 2;i <= sq;++ i){
if (!vis[i]) pri[++ cnt] = i,gp1[cnt] = add (gp1[cnt - 1],i),gp2[cnt] = add (gp2[cnt - 1],mul (i,i));
for (Int j = 1;j <= cnt && i * pri[j] <= sq;++ j){
vis[i * pri[j]] = 1;
if (i % pri[j] == 0) continue;
}
}
for (ll l = 1,r;l <= n;l = r + 1){
r = n / (n / l);w[++ sw] = n / r;g1[sw] = w[sw] % mod;
g2[sw] = dec (1ll * g1[sw] * (g1[sw] + 1) % mod * (2 * g1[sw] + 1) % mod * 166666668 % mod,1);
g1[sw] = dec (1ll * g1[sw] * (g1[sw] + 1) % mod * 500000004 % mod,1);
if (n / r <= sq) id1[n / r] = sw;else id2[r] = sw;
}
for (Int i = 1;i <= cnt;++ i){
ll sqr = 1ll * pri[i] * pri[i];
for (Int j = 1;j <= sw && w[j] >= sqr;++ j){
ll p = w[j] / pri[i];p = (p <= sq ? id1[p] : id2[n / p]);
g1[j] = dec (g1[j],mul (pri[i],dec (g1[p],gp1[i - 1])));
g2[j] = dec (g2[j],mul (mul (pri[i],pri[i]),dec (g2[p],gp2[i - 1])));
}
}
write (add (S (n,0),1)),putchar ('\n');
return 0;
}
```
# 另外的一些题目
## 区间素数个数
[题目传送门](https://loj.ac/problem/6235)
## 题目大意
给出一个 $n$ ，求出 $1\to n$ 的素数个数，$n\le 10^{11}$ 。
## 思路
一开始傻了，以为直接求，然后就发现这个东西其实不是积性函数。但是我们发现，如果我们 $g$ 求的是 $I$ ，那么最后答案就是 $g(n,|\mathbb{P}|)$ 。
时间复杂度自然同上。
# $\texttt{Code}
代码戳这里打开
奇怪的数学题
题目传送门
题目大意
定义 sgcd(n,m) 表示 n,m 的次大公因子，给定 n,k ，求出:
\sum_{i=1}^{n}\sum_{j=1}^{n}sgcd(i,j)^k
答案对 2^{32} 取模。
思路
让我又一次地体会到了 \texttt{Min-25} 筛的毒瘤。。。如果不会可以戳这里学习一波。。。
首先，不难想到 sgcd(i,j)=\dfrac{\gcd(i,j)}{\text{LPF}(\gcd(i,j))}
其中 \text{LPF}(i) 表示 i 的最小质因子。于是，答案就是:
\sum_{d=2}^{n} (\dfrac{d}{\text{LPF}(d)})^k(2\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\varphi(i)-1)
（减 1 是因为 (1,1) 会算两次）
看到这个式子，我们发现后面那个东西显然可以使用杜教筛筛出来，然后直接整除分块即可。考虑前面那个东西，我们这个东西似乎可以 \texttt{Min-25} 筛筛出来，但是这并不是一个积性函数。但是如果我们假设我们要求积性函数 f(x)=x^k,x\in \mathbb{P} 的前缀和，我们观察我们 g(n,i) 的转移：
g(n,i)=g(n,i-1)-\mathbb{P_i}^k(g(\lfloor\frac{n}{\mathbb{P_i}}\rfloor,i-1)-g(\mathbb{P_{i-1}},i-1))
我们发现其实我们除以 \text{LPF}(d) 其实就相当于去掉最小质因数的贡献，在式子就相当于去掉 \mathbb{P_i}^k ，直接累加后面那一坨就好了，如果不理解可以见代码或者不管直接暴力理解 g(n,i) 的含义也可以，就相当于钦定 \mathbb{P_i} 为最小质因数计算贡献。
我们发现还有问题需要解决：
首先第一个问题更好解决，我们发现质数处的取值为 1，即求出质数的个数，可以使用上一道题目的方法解决。
考虑第二个问题，其实就是要求：
(\sum_{i=1}^{n}i^k)-1
这个显然可以使用第二类斯特林数展开得到：
=\sum_{i=1}^{k}\begin{Bmatrix}k\\i\end{Bmatrix}\dfrac{(n+1)^{\underline{i+1}}}{i+1}
这个可以直接暴力斯特林展开，然后再用有限微积分求到。（应该非常好求吧？（伦敦雾
但是这道题是直接自然溢出，所以不好求逆元，于是我们就只好麻烦一个找到 i+1 的倍数除掉之后再乘上去，反正都是 \Theta(k^2) 的。至于为什么我觉得非常显然，考虑剩余系即可。
于是，我们就解决了这道题了。时间复杂度 \Theta(\dfrac{n^{\frac{3}{4}}}{\log n}++n^{\frac{2}{3}}+k^2) ，足以卡过去。
\texttt{Code}
代码戳这里打开
简单的函数
题目传送门
题目大意
给出一个函数 f(x) 满足：
-
f(1)=1
-
f(p^c)=p\oplus c,s.t.\ \ p\in \mathbb{P}
-
f(xy)=f(x)f(y),s.t.\ \ \gcd(x,y)=1
给出 n，求 \sum_{1}^{n} f(i)，n\le 10^{10}
思路
我们发现对于 f(p) ，如果 p\not= 2，那么 f(p)=p-1，于是我们可以用 \texttt{Min-25} 求出这个东西（具体见代码），然后直接按套路做就好了。里面有一个地方需要解释一下，注释里面已经写了。
\texttt{Code}
代码戳这里打开
Sanrd
题目传送门
题目大意
给出 l,r ，求出 :
\sum_{i=l}^{r} f(i)
其中 f(i) 表示 i 的次大质因子。
l\le r\le 10^{11}
思路
我们可以设 S(x,y)=\sum_{i=1}^{x}[\texttt{LPF}(i)>\mathbb{P_y}]f(i)，于是我们就可以得到转移式：
S(x,y)=\sum_{\mathbb{P_i}^e\le x\wedge i>y}(S(\lfloor\frac{x}{\mathbb{P_i}^e}\rfloor)+\mathbb{P_i}\sum_{j\ge i}[j\in \mathbb{P}])
然后我们就可以用 \texttt{Min-25} 筛解决了。
\texttt{Code}
代码戳这里打开
梦中的数论
题目传送门
题目大意
给出 n ，求出：
\sum_{i=1}^{n} \sum_{j=1}^{n} \sum_{k=1}^{n} [(j|i)\wedge ((j+k)|i)]
## 思路
以下 $\sigma(i)$ 表示 $i$ 的因数个数。
我们其实发现题目要求的其实就是：
$$\sum_{i=1}^{n} \binom{\sigma(i)}{2}=(\sum_{i=1}^{n}\sigma^2(i)-\sum_{i=1}^{n}\sigma(i))/2$$
于是问题就是如何求出因子个数平方的前缀和和因子个数的前缀和。显然后面一个简单一点，所以先考虑后者，可以发现答案即为：
$$\sum_{i=1}^{n} \lfloor\frac{n}{i}\rfloor$$
考虑前者，发现它是一个完全积性函数，所以我们就可以使用 $\texttt{Min-25}$ 筛出这个东西，大概就是 $f(p^k)=(k+1)^2$ 。然后就是板子的事情了。
# $\texttt{Code}
代码戳这里打开
P.S.
据说\texttt{Min-25}筛的时间复杂度为\Theta(\frac{n^{\frac{3}{4}}}{\log n})，也有人说是渐线性时间复杂度\Theta(n^{1-\epsilon})，不过据说证实了是前者。空间复杂度离散化之后可以做到\Theta(\sqrt n)。
我们仔细来看\texttt{Min-25}筛如何降低时间复杂度的过程，发现我们用在自变量为质数时相同的完全积性的函数去解决了当取值为质数的时候的值，之后再用积性函数的性质解决合数的和。不得不说，\texttt{Min-25}简直是个天才。\text{Min-25 Orz Orz Orz}
这里解释一下为什么质数只需要筛到\sqrt n，这是因为S函数所需的无非是枚举最小质因数，而最小质因数一定不大于\sqrt n。
话说可以做到 \Theta(n^{\frac{2}{3}}) 甚至更优，但是小蒟蒻并不能看懂，等以后再说吧。。。
$\Theta(\frac{n^{\frac{2}{3}}}{\log n})$ ： 朱震霆的国家集训队论文： 《一些特殊的数论函数求和问题》, 国家集训队2018论文集