在非线形时间内筛某些奇性函数前缀和

狄利克雷卷积

(f∗g)(n)=∑d∣nf(d)g(nd)(f\ast g)(n)=\sum_{d\mid n} f(d)g(\tfrac{n}{d})

一些结论，会用到（ 注: I(n)=1,id(n)=n,ϵ(n)=[n=1]I(n)=1,id(n)=n,\epsilon(n)=[n=1] ）

φ∗I=idμ∗I=ϵμ∗id=φ\begin{aligned} \varphi \ast I=id\\ \mu \ast I=\epsilon\\ \mu \ast id=\varphi \end{aligned}

线性筛 φ,μ\varphi,\mu

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const int N = 100000;
int p[N],tot;
ll phi[N],mu[N];
bool v[N];
void init(int n) {
    for(int i=2;i<=n;++i) {
        if(!v[i]) p[++tot]=i,phi[i]=i-1,mu[i]=-1;
        for(int j=1;j<=tot&&p[j]*i<=n;++j) {
            v[p[j]*i]=1;
            if(i%p[j]==0) {
                mu[i*p[j]]=0;
                phi[p[j]*i]=phi[i]*p[j];
                break;
            }
            mu[p[j]*i]=-mu[i];
            phi[p[j]*i]=phi[i]*(p[j]-1);
        }
    }
}

杜教筛

现在我们要求 ff 的前缀和，记 F(n)=∑i=1nf(i)\displaystyle F(n)=\sum_{i=1}^n f(i) ，我们再找一个积性函数 gg ，(gg 要满足什么性质待会儿再说)

考虑展开 ∑i=1n(f∗g)\sum_{i=1}^n (f\ast g) :

∑i=1n(f∗g)=∑i=1n∑d∣if(d)g(id)根据狄利克雷卷积=∑d=1ng(d)∑i=1⌊n/d⌋f(i)更改求和顺序=∑d=1ng(d)F(⌊n/d⌋)根据定义\begin{aligned} \sum_{i=1}^n (f\ast g) &= \sum_{i=1}^n \sum_{d\mid i} f(d)g(\tfrac{i}{d}) &\text{根据狄利克雷卷积} \\ &= \sum_{d=1}^n g(d)\sum_{i=1}^{\lfloor n/d\rfloor} f(i) & \text{更改求和顺序}\\ &= \sum_{d=1}^n g(d)F(\lfloor n /d\rfloor) & \text{根据定义}\\ \end{aligned}

再考虑 g(1)F(n)g(1)F(n)

g(1)F(n)=∑d=1ng(d)F(⌊n/d⌋)−∑d=2ng(d)F(⌊n/d⌋)两前缀和向减=∑i=1n(f∗g)−∑d=2ng(d)F(⌊n/d⌋)根据之前求的直接代\begin{aligned} g(1)F(n) &=\sum_{d=1}^n g(d)F(\lfloor n /d\rfloor) -\sum_{d=2}^n g(d)F(\lfloor n /d\rfloor)&\text{两前缀和向减}\\ &= \sum_{i=1}^{n} (f\ast g)-\sum_{d=2}^n g(d)F(\lfloor n /d\rfloor)&\text{根据之前求的直接代}\\ \end{aligned}

这就完事了，只要能快速求出 gg 的前缀和，和 f∗gf\ast g 的前缀和，式子右边数论分块再递归求解即可，可以线性筛预处理一部分，同时加上记忆化搜索。

伪代码

1
2
3
4
5
6
7
8
9
10
ll getF(int n) {
    if(n < N) return preF[n]; // N = 1e6 线性筛预处理结果
    if(memF[n]) return memF[n]; // 记忆化
    ll ret = sum_fg(n); // 求出 f*g 前缀和
    for (int i = 2, j; i <= n; i = j + 1) { // 数论分块
        j = n / ( n / i );
        ret -= getF( n / i ) * (sum_g(j) - sum_g( i - 1 ) ); // 递归求解
    }
    return memF[n] = ret;
}

筛欧拉函数

注意到 φ∗I=id\varphi \ast I=id ，I(n)=1,id(n)=nI(n)=1,id(n)=n ，这两前缀和有手就行，直接代公式，得到:

F(n)=n(n+1)2−∑d=2nF(⌊n/d⌋)F(n)=\frac{n(n+1)}{2}-\sum_{d=2}^n F(\lfloor n/d\rfloor) 

1
2
3
4
5
6
7
8
9
10
ll PHI(ll x) {
    if(x<N) return phi[x];
    if(phi_b[x]) return phi_b[x];
    ll ret=(1ll+x)*x/2ll;
    for(ll i=2ll,j;i<=x;i=j+1) {
        j=x/(x/i);
        ret-=PHI(x/i)*(j-i+1ll);
    }
    return phi_b[x]=ret;
}

筛莫比乌斯函数

根据 μ∗I=ϵ\mu\ast I=\epsilon ，I(n)=1,ϵ(n)=[n=1]I(n)=1,\epsilon(n)=[n=1] ，这前缀和一样有手就行。。

F(n)=1−∑d=2nF(⌊n/d⌋)F(n)=1-\sum_{d=2}^n F(\lfloor n/d\rfloor) 

1
2
3
4
5
6
7
8
9
10
ll MU(ll x) {
    if(x<N) return mu[x];
    if(mu_b[x]) return mu_b[x];
    ll ret=1ll;
    for(ll i=2ll,j;i<=x;i=j+1) {
        j=x/(x/i);
        ret-=MU(x/i)*(j-i+1ll);
    }
    return mu_b[x]=ret;
}