U1S1这个东西真的nb

cz_xuyixuan【学习笔记】Min25筛

这个写得好！！！

我们通过一道题来入门

luogu P5325 【模板】Min_25筛

先考虑如何计算\(g(n,i)\)

我们把那个式子拆开，发现是\(f(p)=p^2-p\)

所以我们需要分别计算\(p^2\)的和\(p\)的

设\(g(n,i)=\sum\limits_{j=1}^n[j \in P \ \ or \ \ Min_j >p[i]] * i ^k\)

其中的\(k\)对应为上面的\(1,2\),\(Min_j\)表示\(j\)的最小质因数

可以得到一个显然的转移
考虑把第\(i\)个质数\(p[i]\)的贡献挖掉
\(g(n,i)=g(n,i-1)-p[i]^k*(g(\frac{n}{p[i]^k}, i-1)-sum[i-1])\)
\(sum[i]\)表示前\(i\)个质数的贡献

这样我们就轻易得到了\(g(n,i)\)
显然\(|P|=i\le \sqrt{n}\)，通过这个可以在\(O(\frac{n^{\frac{3}{4}}}{logn})\)的时间复杂度内计算出\(g(n,|P|)\)
即所有质数对答案的贡献

我们再来

设\(S(n,i)=\sum\limits_{j=1}^n[Min_j>p[i]] * f(j)\)

根据最终的定义，我们可以得到
\(\sum\limits_{i=1}^n f(i)=S(n,0)+f(1)\)

然后我们再来考虑如何求\(S(n,i)\)

因为\(f\)是积性函数，质数的部分我们上面已经求出来了，我们可以考虑枚举这个合数的最小值质因数和它的次数来转移

方程同样不难

\(S(n,i)=g(n,|P|)-\sum\limits_{j=1}^{i-1}f(p[j]) + \sum\limits_{j>i \& p[j]^x\le n}(f(p[j]^x,j)+[x>1])\)

意思就是\(g(n,|P|)\)表示所有质数的贡献，因为\(Min_j>p[i]\)所以还要把\(<p[i]\)的质数的贡献减掉

然后枚举合数的最小质因数\(p[j]\),以及次数\(x\)后面的\([x>1]\)加上的是形容\(p^?\)这样的数的贡献

这一部分计算的时间复杂度同样是\(O(\frac{n^{\frac{3}{4}}}{logn})\)

然后就完事了，注意\(1\)要特殊处理

可以看代码理解

关于空间储存问题，我们发现\(n\)一定是\(\large \frac{N}{i}\)中的一个，所以可以提前处理出来
类似分块一样保存，就可以把空间压到\(O(\sqrt{n})\)

code:

#include<bits/stdc++.h>
#define N 200050
#define mod 1000000007
#define ll long long
using namespace std;
int add(int x, int y) { x += y;
    if(x >= mod) x -= mod;
    return x;
}
int sub(int x, int y) { x -= y; 
    if(x < 0) x += mod;
    return x;
}
int mul(int x, int y) {
    return 1ll * x * y % mod;
}
int qpow(int x, int y) {
    int ret = 1;
    for(; y; y >>= 1, x = mul(x, x)) if(y & 1) ret = mul(ret, x);
    return ret;
}
int p[N], sz, s[N][3], vis[N], blo;
void get(int n) {
    for(int i = 2; i <= n; i ++) {
        if(!vis[i]) {
            p[++ sz] = i;
            s[sz][1] = add(s[sz - 1][1], i);
            s[sz][2] = add(s[sz - 1][2], mul(i, i));//预处理sum
        }
        for(int j = 1; j <= sz && p[j] * i <= n; j ++) {
            vis[p[j] * i] = 1;
            if(i % p[j] == 0) break;
        }
    }
}
ll n, w[N];
int id1[N], id2[N], gs, g[N][3];
int id(ll x) {
    if(x <= blo) return id1[x];
    return id2[n / x];
}
ll s1(ll x) { x %= mod;
    return 1ll * x * (x + 1) % mod * qpow(2, mod - 2) % mod;
}
ll s2(ll x) { x %= mod;
    return 1ll * x * (x + 1) % mod * (2 * x + 1) % mod * qpow(6, mod - 2) % mod;
}
ll f(ll x) { x %= mod;
    return mul(x, sub(x, 1));
}
ll S(ll n, int m) {
    if(n <= p[m]) return 0;
    int ret = sub(sub(g[id(n)][2], s[m][2]), sub(g[id(n)][1], s[m][1]));//即p^2-p
    for(int j = m + 1; j <= sz && p[j] <= n / p[j]; j ++) {
        ll x = p[j];
        for(int k = 1; x <= n; x = x * p[j], k ++) {
            ret = add(ret, mul(f(x), S(n / x, j) + (k > 1)));//把上面两个放在一起转移了,因为积性函数的和还是积性函数
        }
    }
     return ret;
}
int main() {
    scanf("%lld", &n);
    
    get(blo = sqrt(n));
    for(ll l = 1, r = 0; l <= n; l = r + 1) {
        r = n / (n / l);
        w[++ gs] = n / l;
        g[gs][1] = sub(s1(w[gs]), 1);
        g[gs][2] = sub(s2(w[gs]), 1);//维护k=1，2,这里的g是g(n,0)
        if(w[gs] <= blo) id1[w[gs]] = gs;//类似分块一样储存
        else id2[n / w[gs]] = gs;
    }

    for(int i = 1; i <= sz; i ++) {
        for(int j = 1; j <= gs && p[i] <= w[j] / p[i]; j ++) {//g的转移，把第二维滚掉了
            g[j][1] = sub(g[j][1], mul(p[i], sub(g[id(w[j] / p[i])][1], s[i - 1][1])));
            g[j][2] = sub(g[j][2], mul(mul(p[i], p[i]), sub(g[id(w[j] / p[i])][2], s[i - 1][2])));
        }
    }
    printf("%d", add(S(n, 0), 1));
    return 0;
}