min25筛学习笔记
Minuses
·
·
个人记录
orzhq！！
min25的功能好像和杜教筛差不多？都是处理积性函数前缀和。
但是这个min25筛她的复杂度是 O(\frac{n^{\frac 3 4}}{logn}) 的，感觉没有杜教筛优秀，但是她肯定能处理什么杜教筛不能处理的问题吧？（不懂）
基本思路？
\sum_{i=1}^n f(i)
\forall x\perp y,f(xy)=f(x)f(y)
然后min25干了一件事，他把 f 的求和拆成质数和合数，然后分别考虑，就比较妙。
质数部分
\sum_{2\le p\le n} f(p)
min25采用了dp，其实就是个类似于埃氏筛的东西
我们令 g(i,j) 表示前 i 个数当中，minp(i)>p_j 的数的 F(i) 之和，其中 F(i) 满足，F(p)=f(p)，且 F 为完全积性函数，且 F 的前缀和容易计算。（基本就是多项式）
转移大概就是考虑筛掉一个质数，那么我们可以把所有整除 p_j 的数挑出来，这些数当中，除了原本就是质数的数以外，其它的数都会在这一次被筛掉，又因为 F 完全积性，所以...
g(i,j)=g(i,j-1)-F(p_j)\left[g(\lfloor\frac{i}{p_j}\rfloor,j-1)-\sum_{2\le p\le p_{j-1}}F(p)\right]
从左往右解释一遍，首先我们要筛掉 p_j，那么我们就要把 p_j 提出来剩下了 1,2,3,4\dots,\lfloor \frac{i}{p_j}\rfloor。这些数当中所有已经被 j-1 筛掉的数都可以被选，但是他实际上还算到了所有 [1,j-1] 里的质数，而这些其实是应该被筛掉的，所以杀掉他。
边界条件是 p_j^2 \le n，此时显然 g 直接继承。
然后还有就是 g(n,0)=\sum_{1\le i\le n} F(i)，这个可以用 F 的性质快速算出（一般都是求和公式）。
然后我们就可以递推得到 g(i,+\infty)，实际上取到 \sqrt{i} 就够了。
注意到我们可以把 j 这一维滚掉。然后 i 这一维就直接整除分块吧...
合数部分
这一部分其实跟前面比较类似，不过用到的是把最小质因数拆出来。
显然 $S(n,1)+f(1)$ 就是答案。
我们考虑去枚举当前这个质数贡献了几次幂，把所有能贡献到的合数全部加回来。（感觉比质数更容易理解一点？）
$$
S(i,j)=g(i,+\infty)-\sum_{k=1}^{j - 1}f(p_k)+\sum_{e\ge 1,p_k^{e+1}\le i,k\ge j}f(p_k^e)S(\frac{n}{p_k^e},k+1)+f(p_k^{e+1})
$$
这个东西就是考虑先把质数搞出来，然后加上合数的贡献，也就是枚举所有合数当中最小质因子大于等于 $j$ 的数，然后枚举其次数把它提出来，注意到我们没有统计 $p_k^i$ 这种形式的数，那么加上就可以了。
这部分代码据说直接递归处理复杂度就是对的。
## 实现
这个玩意感觉不是很好实现的样子...
首先我需要先想想这玩意怎么dp，首先你会发现这个东西其实有用的 $g$ 只有根号个，可以数论分块，然后我们可以把 $j$ 套在外面，这样就可以对于每个 $j$ 一遍一遍做了。
然后S直接dp应该就没什么好说的了吧..
```cpp
#include <bits/stdc++.h>
using namespace std;
namespace Minus {
typedef long long ll;
const int maxn = 1e6 + 9, N = 1e6;
const ll mod = 1e9 + 7;
ll n, m;
int id1[maxn], id2[maxn], tot;
int getid(ll x) { return x <= m ? id1[x] : id2[n / x]; }
int np[maxn], ptot;
ll prime[maxn];
void init() {
for (int i = 2; i <= N; ++i) {
if (!np[i]) prime[++ptot] = i;
for (int j = 1; j <= ptot && i * prime[j] <= N; ++j) {
np[i * prime[j]] = 1;
if (i % prime[j] == 0) break;
}
}
}
ll g1[maxn], g2[maxn], w[maxn];
ll ksm(ll a, ll b) {
ll ret = 1;
for (; b; b >>= 1, a = a * a % mod) if (b & 1) ret = ret * a % mod;
return ret;
}
const ll inv2 = ksm(2, mod - 2), inv6 = ksm(6, mod - 2);
ll sum1[maxn], sum2[maxn];
ll f(ll x) { return x * (x - 1 + mod) % mod; }
ll getans(ll i, int j) {
if (prime[j] > i || i <= 1) return 0;
int x = getid(i);
ll ret = (((g2[x] - g1[x] + mod) % mod) - ((sum2[j - 1] - sum1[j - 1] + mod) % mod) + mod) % mod;
for (int k = j; k <= ptot && prime[k] * prime[k] <= i; ++k) {
ll now1 = prime[k], now2 = prime[k] * prime[k];
for (; now2 <= i; now1 = now2, now2 *= prime[k]) {
ret = (ret + (f(now1 % mod) * getans(i / now1, k + 1) % mod + f(now2 % mod)) % mod) % mod;
}
}
return ret;
}
int main() {
init();
scanf("%lld", &n);
m = sqrt(n);
for (ll l = 1, r; l <= n; l = r + 1) { // 搞出来所有g的初始
r = n / (n / l);
w[++tot] = (n / l);
if ((n / l) <= m) id1[w[tot]] = tot;
else id2[n / w[tot]] = tot;
ll v = w[tot] % mod;
g1[tot] = v * (v + 1) % mod * inv2 % mod;
g2[tot] = v * (v + 1) % mod * (2 * v % mod + 1) % mod * inv6 % mod;
g1[tot] = (g1[tot] - 1 + mod) % mod; // 别忘了干掉1
g2[tot] = (g2[tot] - 1 + mod) % mod;
}
for (int j = 1; j <= ptot; ++j) {
sum1[j] = (sum1[j - 1] + prime[j]) % mod;
sum2[j] = (sum2[j - 1] + prime[j] * prime[j] % mod) % mod;
}
for (int j = 1; prime[j] <= m; ++j) {
for (int i = 1; i <= tot && prime[j] * prime[j] <= w[i]; ++i) {
g1[i] = (g1[i] - prime[j] * ((g1[getid(w[i] / prime[j])] - sum1[j - 1] + mod) % mod) % mod + mod) % mod;
g2[i] = (g2[i] - prime[j] * prime[j] % mod * ((g2[getid(w[i] / prime[j])] - sum2[j - 1] + mod) % mod) % mod + mod) % mod;
}
}
// printf("%lld\n", (g2[1] - g1[1] + mod) % mod);
printf("%lld\n", (getans(n, 1) + 1) % mod);
return 0;
}
}
int main() {
return Minus::main();
}
```