用途&复杂度
min25筛可用于计算一些积性函数的前缀和。
要求：f(p)，（p 为质数），是一个关于 p 的项数较少的多项式，或可以快速求值。f(pc) 可以快速求值。
复杂度：O(lognn43)。
min25筛与杜教筛都可以计算积性函数的前缀和，且新的min25筛复杂度也是 O(n32)。但是使用杜教筛需要构造出一个积性函数 g(i)，使得 f∗g 可以快速求出前缀和。而使用min25筛则只要满足上面的要求即可。
原理
设 f(i) 为题中需要求前缀和的积性函数，p 为某个质数。
分为两步：
- 对于所有 x=⌊dn⌋，（也就是数论分块里的那个数），求出不超过 x 的所有质数的 f 值之和。即 ∑p≤xf(p)。
- 求解原问题，即对于所有 x=⌊dn⌋，求出不超过 x 的所有数的 f 值之和。即 ∑i=1xf(i)。
预处理：
需要先处理出小于等于 n 的所有质数。
设 Pi 表示从小到大第 i 个质数，P1=2。
第一步
记 g(i)=f(i)。为啥还要再搞一个？因为这里的 i 是任意数（包括非质数），也就是说把任意数都套进 f(i)，i 为质数 里。而实际上真正的 f 在非质数上已经有定义了，且很可能不等于质数时的式子，所以这里另设了一个 g。
记 lpf(i) 为 i 的最小质因数。
记 G(i,j) 为 ≤i 的所有质数以及最小质因子 >Pj 的合数的 g 值之和。即 ∑k=1ig(k)[k∈prime∣∣lpf(k)>Pj]。
则有对于任意 i，G(i,0)=∑k=2ig(k)。
第一步的目的就是求 G(i,j)。
考虑递推从 G(n,j−1) 求出 G(n,j)。
从 j−1 变为 j 少了那些以 Pj 为最小质因子的合数的 g 值。
-
如果 Pj2>n，则不存在以 Pj 为最小质因数的合数，结果也就没有变化，所以 G(n,j)=G(n,j−1)。
-
如果 Pj2≤n，所有要去掉的合数的最小质因子都是 Pj，把 Pj 提出来，则需要减去的部分是 g(Pj)⋅G(Pjn,j−1)，但是别忘了，G(n,j) 中还包含了所有小于等于 n 的质数，这些质数不应该被去掉，所以还要再补回来，即加上 ∑i=1j−1g(Pi)，也可以写成 G(Pj−1,j−1)。
其实这里还有个问题，为什么可以把 Pj 提出来？但是我也不会 大概是因为最开始限定了g(p)=f(p) 是 p 的低次多项式，参考 OIWiKi 。或者把 f(p) 实例化成 ps，理解起来方便些。
把上面两种情况合并，又由于 g(p)=f(p)。
综上
G(i,0)=k=2∑ig(k)
G(n,j)={G(n,j−1)G(n,j−1)−f(Pj)[G(Pjn,j−1)−∑i=1j−1f(Pi)]Pj2>nPj2≤n
第二步
记 S(i,j) 表示 ≤i 的所有最小质因子大于等于 Pj 的数的 f 值之和。这里令 lcp(p)=p，即质数的最小质因子为它自己。
所以 S 同样可以分成质数和合数两部分。
先考虑质数部分。
由第一步可以求出 G(n,∣p∣)，其中 ∣p∣ 为小于等于 n 的质数个数，在预处理部分可以得到。G(n,∣p∣) 实际上是所有质数的 f 值之和，即 ∑pf(p)，但是我们需要的是大于等于 Pj 的质数，所以要减去 ∑i=1j−1f(Pi) 。所以质数部分的结果为
G(n,∣P∣)−i=1∑j−1f(Pi)
再考虑合数部分。
对于每个合数，枚举它的最小质因子，以及包含这个最小质因子的次数。
k≥j∑e≥1∑f(Pke)S(Pken,k+1)
要注意，这里可以提出来和上面的原因不同，这里是因为已经限制了剩下的部分最小质因子大于等于 Pk+1， 所以是互质的，由于是积性函数，所以可以直接把结果相乘。
但是，如果一个数只有一个质因子？ x=pk ？所以还要再补上一部分 f(Pke+1)。为啥是 e+1 ？因为 p1 是质数，之前算过了，而 Pie+1 一定是 ≤n 的，也需要加进来，所以就是 ∑e≥1f(Pke+1).
综上，合数部分真正的结果是
k≥j∑e≥1∑f(Pke)S(Pken,k+1)+f(Pke+1)
至此，第二步的递推式也得到了。
S(i,∣P∣)=G(i,∣P∣)
S(n,j)=G(n,∣P∣)−i=1∑j−1f(Pi)+k≥j∑e≥1∑f(Pke)S(Pken,k+1)+f(Pke+1)
最后一步
虽然两步的式子都推出来了，但是如果要实现的话，需要枚举每一个 i≤n 和 j≤∣P∣，i 的复杂度显然不行。
但是可以发现每次 n 出现的地方都是 ⌊xn⌋，所以其实只需要计算 G(⌊xn⌋)，且递归求 S 的过程中也只涉及到了 ⌊xn⌋。数论分块告诉我们这个的个数是 O(n) 的。
最终答案就是 S(n,1)+f(1)，因为 1 的值之前一直没算。
再来理一遍流程。
首先预处理出所有 ≤n 的质数，同时得到它们的前缀和（指只有质数的和）。
由于我们只需要 G(⌊xn⌋,j)，所以数论分块，对于每个 i=⌊xn⌋，快速求出 G(i,0)，也就是把 f 中质数的式子应用到任意数时的前缀和。再通过第一步的递推式求出所有 G(⌊xn⌋,j)。其目的是为了得到 G(i,∣P∣)，作为第二步递推的初始值。
由此也可以看出，我们求第一步的目的就在于求出所有质数的 f 的前缀和。而也有题目也仅仅要求 f 在质数时的前缀和，这时就只需要求第一步了。
最后通过第二步的递推式求出 S(n,1)。答案为 S(n,1)+f(1)。
例题
题意：f 为积性函数，且 f(pc)=p⊕c，求前缀和。
这里实际上是求了素数个数以及素数和。
先考虑质数的 f 值。f(p)=p⊕1，由于除了 2 外的质数都是奇数，这时 g(p)=f(p)=p−1，这个 g 不是积性函数，不能直接筛，所以要把 f(p) 拆成 f1(p)=p,f2(p)=1，则 f(p)=f1(p)+f2(p)。
f1 就是素数和，f2 就是素数个数，分别求出 G1,G2，再代入第二步求 S。
要注意维护 ⌊xn⌋ 时由于可能会过大，所以要存在 ⌊xn⌋ 与 n/⌊xn⌋ 这两者中较小的下标处，这只是为了存下，与用map存一样，但是map会带来额外的 log，所以不行。
当 p=2 时，f(p)=3，但是我们算的是 1，所以当 j=1，即包含质因子 2 时，res 要加 2。
最后要加上 f(1)。
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
| #include <bits/stdc++.h>
using namespace std;
#define ll long long
#define debug(x) cout << #x << ":\t" << x << endl;
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
ll n, sqr;
int vis[N], tot;
ll prime[N], sump[N];
void pre(ll n) {
for (int i = 2; i <= n; i++) {
if (!vis[i]) {
prime[++tot] = i;
sump[tot] = (sump[tot - 1] + i) % mod;
}
ll d;
for (int j = 1; j <= tot && (d = i * prime[j]) <= n; j++) {
vis[d] = 1;
if (i%prime[j] == 0)break;
}
}
}
ll w[N]; int m;
ll g[N], h[N];
int id[2][N];
ll f(ll x, int y) {
return x ^ y;
}
ll S(ll x, int j) {
if (x <= 1 || x < prime[j])return 0;
int k = (x <= sqr ? id[0][x] : id[1][n / x]);
ll res = (g[k] - sump[j - 1] - h[k] + j - 1 + 2 * mod) % mod;
for (int i = j; i <= tot && prime[i] * prime[i] <= x; i++) {
ll t = prime[i];
for (int e = 1; t*prime[i] <= x; e++, t *= prime[i]) {
res = (res + f(prime[i], e)*S(x / t, i + 1) % mod + f(prime[i], e + 1)) % mod;
}
}
return res;
}
int main() {
scanf("%lld", &n);
sqr = (ll)sqrt(n);
pre(sqr);
for (ll i = 1, j; i <= n; i = j + 1) {
j = n / (n / i);
w[++m] = n / i;
if (w[m] <= sqr)id[0][w[m]] = m;
else id[1][n / w[m]] = m;
g[m] = w[m] % mod*((w[m] + 1) % mod) % mod*inv2 % mod;
g[m] = (g[m] - 1 + mod) % mod;
h[m] = (w[m] - 1 + mod) % mod;
}
for (int j = 1; j <= tot; j++) {
for (int i = 1; i <= m && w[i] >= prime[j] * prime[j]; i++) {
int k = (w[i] / prime[j] <= sqr ? id[0][w[i] / prime[j]] : id[1][n / (w[i] / prime[j])]);
ll tmp = prime[j]*(g[k] + mod - sump[j - 1]) % mod;
g[i] = (g[i] + mod - tmp) % mod;
tmp = (h[k] - (j - 1) + mod) % mod;
h[i] = (h[i] + mod - tmp) % mod;
}
}
printf("%lld\n", (S(n, 1) + 1) % mod);
return 0;
}
|
2020CCPC网络赛1002
题意：节点 1 到 n，连边的边权为 lcm(i+1,j+1)，求最小生成树。
图论部分直接跳过。
最终转化为求 ∑i=3n+1i+∑p=3np[p∈prime]。也就是要求质数和。
不能取模！取模会超时！！素数和不会爆ll。
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
| #include <bits/stdc++.h>
using namespace std;
#define ll long long
#define debug(x) cout << #x << ":\t" << x << endl;
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
ll mod = 1e9 + 7;
ll inv2 = (mod + 1) / 2;
int T;
ll n, sqr;
int vis[N], tot;
ll prime[N], sump[N];
void pre(ll n) {
tot = 0;
for (int i = 1; i <= n; i++)vis[i] = 0;
for (int i = 2; i <= n; i++) {
if (!vis[i]) {
prime[++tot] = i;
sump[tot] = (sump[tot - 1] + i);
}
ll d;
for (int j = 1; j <= tot && (d = i * prime[j]) <= n; j++) {
vis[d] = 1;
if (i%prime[j] == 0)break;
}
}
}
ll g[N], w[N]; int m, id[2][N];
int main() {
pre(200000);
scanf("%d", &T);
while (T--) {
scanf("%lld%lld", &n, &mod);
n++;
sqr = (ll)sqrt(n);
inv2 = (mod + 1) / 2;
ll ans = (3 + n) % mod*((n - 2) % mod) % mod*inv2%mod;
m = 0;
for (ll l = 1, r; l <= n; l = r + 1) {
r = n / (n / l);
w[++m] = n / l;
if (w[m] <= sqr)id[0][w[m]] = m;
else id[1][n / w[m]] = m;
g[m] = w[m] * (w[m] + 1) / 2 - 1;
}
for (int j = 1; j <= tot; j++) {
for (int i = 1; i <= m && w[i] >= prime[j] * prime[j]; i++) {
int k = (w[i] / prime[j] <= sqr ? id[0][w[i] / prime[j]] : id[1][n / (w[i] / prime[j])]);
ll tmp = prime[j] * (g[k] - sump[j - 1]);
g[i] = g[i] - tmp;
}
}
ans = (ans + g[1] - 2 + mod) % mod;
printf("%lld\n", ans);
}
return 0;
}
|
