@xiaoziyao 2021-07-07T03:11:35.000000Z 字数 2740 阅读 765

min25筛学习笔记

数学 学习笔记

前言

线性筛以 $O(n)$ 的复杂度完成了数论函数的 $[1,n]$ 值域内求值，可是若要以更低的复杂度解决前缀求值，就要考虑更优的筛法了，例如杜教筛，Powerful Number，可是这两个筛法对函数都有较高的要求，于是我们要掌握更普适的筛子——min25筛。

min25筛可以以 $O(\frac{n^{\frac{3}{4}}}{\log n})$ （一说 $O(n^{1-\epsilon})$ ，最新版本好像是 $O((\frac{n}{\log n})^{\frac{2}{3}})$ ）质数幂次上值为一个多项式的积性函数的前缀和。

模板

模板题：P5325 【模板】Min_25筛

题意：给定一个积性函数 $f(x)$ ，满足 $f(p^k)=p^k(p^k-1)(p\in\mathbb{P})$ ，求

$\sum_{i=1}^nf(i)$

定义 $LPF(x)$ 为 $x$ 的最小质因子， $p_i$ 为第 $i$ 个素数。

实际上，min25筛解决的问题可以解决 $f(p^k)$ 是阶为常数的任意多项式的情况，本题只是一种特殊情况。

我们考虑对质数和合数分开考虑，后面的合数枚举其最小质因子及其幂次：

$\sum_{i=1}^n f(i)=\sum_{p\in\mathbb{P},1\leqslant p\leqslant n} f(p)\\+\sum_{p\in P,1\leqslant p\leqslant \sqrt n,1\leqslant p^k\leqslant n}f(p^k)(\sum_{LPF(a)>p,1\leqslant a\leqslant n}f(a)+[k>1])$

前面 $k$ 枚举到 $\sqrt n$ 是因为任意合数的 $LPF$ 一定小于等于 $\sqrt n$ ，后面那个 $k>1$ 是为了不算入 $f(p)$ 而算入 $f(p^k)$ 。

考虑对于每个单项式，设其幂次为 $r$ ，设函数 $g(n,k)$ 在素数上拟合 $f$ ，即 $g(n,k)=\sum_{i=1}^n[i\in\mathbb{P}\vee LPF(i)>p_k]x^r$ 。

考虑 $g(n,k)$ 怎么从 $g(n,k-1)$ 转移过来，不难发现 $p_{k-1}^2>n$ 时 $g(n,k)=g(n,k-1)$ ，否则要减去 $LPF(i)=p_k$ 的贡献，而这个贡献容斥一下就是 $p_k^r(g(\lfloor\frac{n}{p_k}\rfloor,i-1)-g(p_{i-1},i-1))$ （考虑提出质因子，然后减去 $g$ 中多算的素数），即：

$g(n,k)=\begin{cases}g(n,k-1)&p_{k-1}^2>n\\g(n,k-1)-p_k^r(g(\lfloor\frac{n}{p_k}\rfloor,i-1)-g(p_{i-1,i-1}))&\text{otherwise}\end{cases}$

根据上面的素数合数分开算的式子，设

$S(n,k)=\sum_{i=1}^n[LPF(i)>p_k]f(i)\\=g(n,\pi(n))-\sum_{i=1}^{k-1}f(P_i)+\sum_{t>i\wedge p_t^w\leqslant n}f(p_t^w)(S(\lfloor\frac{n}{p_t^w}\rfloor,w)+[w>1])$

本题Powerful Number写法是 $O(n^{\frac{2}{3}})$ 的，但由于常数原因，我的min25比我的Powerful Number快一倍以上。

#include<stdio.h>
#include<math.h>
const int maxt=100005,mod=1000000007,inv2=(mod+1)/2,inv6=(mod+1)/6;
int t,cnt,tot;
long long n;
int sum1[maxt],sum2[maxt],p[maxt],c[maxt],id[maxt][2],g1[maxt<<1],g2[maxt<<1];
long long val[maxt<<1];
inline int add(int a,int b){
    return a+b>=mod? a+b-mod:a+b;
}
int S(long long v,int k){
    if(p[k]>=v)
        return 0;
    int w=id[v<=t? v:(n/v)][v>t],res=add(add(g2[w],mod-sum2[k]),mod-add(g1[w],mod-sum1[k]));
    for(int i=k+1;i<=cnt&&1ll*p[i]*p[i]<=v;i++)
        for(long long j=1,mul=p[i];mul<=v;j++,mul*=p[i])
            res=add(res,1ll*mul%mod*((mul-1)%mod)%mod*(S(v/mul,i)+(j>1))%mod);
    return res;
}
int main(){
    scanf("%lld",&n),t=sqrt(n),c[1]=1; 
    for(int i=2;i<=t;i++){
        if(c[i]==0)
            p[++cnt]=i,sum1[cnt]=add(sum1[cnt-1],i),sum2[cnt]=add(sum2[cnt-1],1ll*i*i%mod);
        for(int j=1;j<=cnt&&i*p[j]<=t;j++){
            c[i*p[j]]=1;
            if(i%p[j]==0)
                break;
        }
    }
    for(long long L=1,R;L<=n;L=R+1){
        long long v=n/L;
        int w=v%mod;
        R=n/v,val[++tot]=v,id[v<=t? v:R][v>t]=tot;
        g1[tot]=add(1ll*w*(w+1)%mod*inv2%mod,mod-1),g2[tot]=add(1ll*w*(w+1)%mod*(w+w+1)%mod*inv6%mod,mod-1);
    }
    for(int i=1;i<=cnt;i++)
        for(int j=1;j<=tot&&1ll*p[i]*p[i]<=val[j];j++){
            long long v=val[j]/p[i];
            int w=id[v<=t? v:(n/v)][v>t];
            g1[j]=add(g1[j],mod-1ll*p[i]*add(g1[w],mod-sum1[i-1])%mod);
            g2[j]=add(g2[j],mod-1ll*p[i]*p[i]%mod*add(g2[w],mod-sum2[i-1])%mod);
        }
    printf("%d\n",add(S(n,0),1));
    return 0;
}