Min_25筛

Posted on Edited on In Word count in article: 1.6k Reading time ≈ 6 mins.
一篇十分无助的学习笔记

Min_25筛

简介

用来处理积性函数前缀和的不错选择， 时间复杂度为\(O(\frac{n^{\frac 34}}{\log_2n})\)，空间复杂度为\(O(\sqrt n)\)

限制：要求质数\(p\)处的函数值是个多项式，且\(p^k\)处的函数值也容易计算

规定：

  • \(\mathbb{P}\)表示素数集合
  • \(cnt\)表示\(n\)范围内的素数个数
  • \(p_i\)表示第\(i\)个素数，特别的\(p_0=0\)
  • \(lpf(x)\)表示\(x\)的最小质因子
  • \(F(x)\)是我们要求的一个积性函数
  • \(f(i)\)是我们构造出来的计算方式与\(F(x)\)相似的完全积性函数

计算方式

大致思路是将\(F(x)\)分为两部分来考虑，一部分是素数，另一部分是合数

Step 1

  • 先考虑求解： \[ \sum_{i=1}^{cnt}F(p_i)=\sum_{x=1}^nF(x)[x\in \mathbb{P}] \]

  • 定义二元函数\(g\)： \[ g(n,j)=\sum_{i=2}^nf(i)[i\in \mathbb{p}\;\lor\; lpf(i)>p_j] \]

注：

  • 这里的\(f(i)\)的具体计算方式与\(i\in\mathbb{p}\)时的\(F(i)\)的计算方式相同，如当\(F(x)=\varphi(x)\)时\(f(x)=x-1\)，即得到的应当是一个完全积性函数

  • 所以我们可以发现，当且仅当\(j=cnt\)时，所求得的值才是要求的值

  • 这里可以易证\(lpf(i)\le \sqrt n\)，即若\(lpf(j)^2\ge n\)，则\(g(n,j)=g(n,j-1)\)，因为不存在\(lpf(i)>p_j\)， 否则： \[ g(n,j)=g(n,j-1)-f(p_j)\cdot\big(g(\frac{n}{p_j},j-1)-g(p_{j-1},j-1)\big) \]

证明： \[ \begin{align*} g(n,j)&=\sum_{i=2}^nf(i)[i\in\mathbb{P}\;\lor\;lpf(i)>p_j]\\ g(n,j-1)&=\sum_{i=2}^nf(i)[i\in\mathbb{P}\;\lor\;lpf(i)>p_{j-1}]\\ \end{align*} \]

  • 那么我们就可以发现，从\(j-1\)递推到\(j\)的过程中，我们多计算了一部分贡献，就是\(i\notin \mathbb{P} \;\land\; i\ne 1 \;\land\; lpf(i)=p_j\)这一部分的贡献

  • 所以我们要减去它们

  • 那么这一部分共有的特点就是都存在最小的质因子\(p_j\)

  • 那么我们就可以先把\(f(p_j)\)提出来

  • 即剩下的部分的贡献可以表示为：\(\big(g(\frac n{p_j},j-1)-g(p_j-1,j-1)\big)\)

  • 关于

  • \[ f(p_j)\cdot g(p_{j-1},j-1) \]

  • 这一部分又可以写为:

  • \[ \sum_{i=1}^{j-1}f(p_i\cdot p_j) \]

  • 发现这一部分的数并满足上文所说的\(i\notin \mathbb{P} \;\land\; i\ne 1 \;\land\; lpf(i)=p_j\)，所以这不能减，得消掉

  • 于是就得到了\(g\)的递推式，进而可以将空间压缩至\(\sqrt n\)

  • 对于\(g\)的第一维，其实只有\(\frac n1,\frac n2,\frac n3\cdots\frac nn\)这些值有被用到。观察递推式，第一位的转移只有\(n\rightarrow \frac np\)，而下取整又满足结合律：

  • \[ \left\lfloor\frac{\lfloor\frac {n}{a}\rfloor}{b}\right\rfloor=\left\lfloor\frac{n}{ab}\right\rfloor \]

  • 所以无论怎样，这个函数只会用到那么\(\sqrt n\)个值

  • 对于\(g\)的第二维，转移只有\(j\rightarrow j-1\)，与此同时第一位也在缩小，所以我们从大到小更新，就可以直接滚掉第二维

据说这一步的时间复杂度就是\(O(\frac{n^{\frac {3}{4}}}{\log_2n})\)

Step 2

现在，我们要求的就是

\[ ans=\sum_{i=1}^nf(i) \]

  • 定义二元函数\(S\)：

  • \[ S(n,j)=\sum_{i=2}^nF(i)[lpf(i)> p_j] \]

  • 显然\(ans=S(n,0)\)

  • 考虑将答案拆分成素数和合数两个部分计算

  • 显然素数部分的贡献为

  • \[ S(n,j)_{素}=g(n,cnt)-g(p_j,j) \]

  • 在考虑合数部分：枚举一批数的最小质因子为\(p_k\)，指数为\(e\)，那么就可以不重复的计算\(lpf(i)\ge p_k\)的合数

  • 因为枚举了幂次，所以将\({p_k}^e\)提出来后，这批数就没有质因子\(p_k\)了，就可积了

  • 注意，\({p_k}^e\)并没有被看作合数，所以贡献是还要加上去的

  • 不用记忆化，直接递归计算即可，边界为\(p_j >n,S(n,j)=0\)

  • \[ S(n,j)=g(n,cnt)-g(p_j,j)+\sum_{k=j}^{p_k^2\le n}\sum_{e=1}^{p_k^e\le n}F(p_k^e)(S(\left\lfloor\frac n{p_k^e}\right\rfloor,k)+[e\ne1] \]

  • 总时间复杂度为\(O(\frac{n^{\frac {3}{4}}}{\log_2n})\)

时间复杂度分析

\[ \begin{aligned} T(n) &= \sum_{i^{2} \le n} O\left(\pi\left(\sqrt{i}\right)\right) + \sum_{i^{2} \le n} O\left(\pi\left(\sqrt{\frac{n}{i}}\right)\right) \\ &= \sum_{i^{2} \le n} O\left(\frac{\sqrt{i}}{\ln{\sqrt{i}}}\right) + \sum_{i^{2} \le n} O\left(\frac{\sqrt{\frac{n}{i}}}{\ln{\sqrt{\frac{n}{i}}}}\right) \\ &= O\left(\int_{1}^{\sqrt{n}} \frac{\sqrt{\frac{n}{x}}}{\log{\sqrt{\frac{n}{x}}}} \mathrm{d} x\right) \\ &= O\left(\frac{n^{\frac{3}{4}}}{\log{n}}\right) \end{aligned} \]

直接表示看不懂好吧，跑路了

例题：

Min_25筛

题目大意：

求：\(\sum_{i=1}^nF(i)\)

其中\(\forall p\in \mathbb{P}\quad\forall k\in[1,\inf]\quad F(p^k)=p^k(p^k-1)\)

Solution

那么我们可以直接另\(f(i) = i(i-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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll maxn = 1e6 + 10;
const ll mod = 1e9 + 7;
const ll inv = 166666668;

ll n;
ll sq, tot, pr[maxn], id1[maxn], id2[maxn], w[maxn];
ll cnt, sum1[maxn], sum2[maxn], g1[maxn], g2[maxn];
bool vis[maxn];

inline void inc(ll &x, ll y)
{
    x += y;
    if (x >= mod) x -= mod;
}

inline ll add(ll x, ll y)
{
    ll temp = x + y;
    return temp >= mod ? temp - mod : temp;
}

inline void init()
{
    sq = sqrt(n);
    for (ll i = 2; i <= sq; ++i) {
        if (!vis[i]) pr[++cnt] = i;
        for (ll j = 1; j <= cnt && pr[j] * i <= sq; ++j) {
            vis[i * pr[j]] = 1;
            if (!(i % pr[j])) break;
        }
    }

    for (ll i = 1; i <= cnt; ++i)
        inc(sum1[i], add(sum1[i - 1], pr[i])),
        inc(sum2[i], add(sum2[i - 1], 1ll * pr[i] * pr[i] % mod));
}

inline ll id(ll x)
{
    if (x <= sq) return id1[x];
    return id2[n / x];
}

inline ll f1(ll x)
{
    x %= mod;
    return x * (x + 1) / 2 % mod;
}

inline ll f2(ll x)
{
    x %= mod;
    return x * (x + 1) % mod * (2 * x % mod + 1) % mod * inv % mod;
}

ll S(ll x, ll j)
{
    if (pr[j] > x) return 0;
    ll ans = ((g2[id(x)] - g1[id(x)] + mod) % mod - (sum2[j] - sum1[j] + mod) % mod + mod) % mod;
    for (ll i = j + 1; i <= cnt && 1ll * pr[i] * pr[i] <= x; ++i)
        for (ll e = 1, sp = pr[i]; sp <= x; sp *= pr[i], ++e)
            ans = (ans + sp % mod * (sp % mod - 1) % mod * (S(x / sp, i) + (e > 1)) % mod) % mod;
    return ans;
}

signed main()
{
    scanf ("%lld", &n);
    init();

    for (ll l = 1, r; l <= n; l = r + 1) {
        r = n / (n / l);
        w[++tot] = n / l;
        g1[tot] = f1(w[tot]) - 1, g2[tot] = f2(w[tot]) - 1;
        if (w[tot] <= sq) id1[w[tot]] = tot;
        else id2[n / w[tot]] = tot;
    }

    for (ll i = 1; i <= cnt; ++i)
        for (ll j = 1; j <= tot && 1ll * pr[i] * pr[i] <= w[j]; ++j) {
            ll k = id(w[j] / pr[i]);
            g1[j] = (g1[j] - pr[i] * (g1[k] - sum1[i - 1]) % mod + mod) % mod;
            g2[j] = (g2[j] - 1ll * pr[i] * pr[i] % mod * (g2[k] - sum2[i - 1]) % mod + mod) % mod;
        }

    printf ("%lld\n", (S(n, 0) + 1) % mod);
    system("pause");
}

参考资料：

JKLover(姥爷的原味博客)

OI-wiki不是给人看的好东西