专栏文章

题解：P4213 【模板】杜教筛

ccogimyun
P4213题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minhq1h8
此快照首次捕获于
2025/12/02 02:36
3 个月前
此快照最后确认于
2025/12/02 02:36
3 个月前
查看原文

前置知识

积性函数

顾名思义，积性函数是一类满足 f(ab)=f(a)×f(b)f(ab)=f(a)\times f(b) 的函数，当然 f(ab)=f(a)×f(b)f(ab)=f(a)\times f(b) 是有成立条件的，它的成立条件是 gcd⁡(a,b)=1\gcd(a,b)=1。

线性筛

可以用 O(n)O(n) 的时间复杂度筛出积性函数 f(x),x∈[1,n]f(x),x\in[1,n] 的值。既然都来学习杜教筛了，一定会线性筛了吧。 代码如下：
CPP
const int N=1e7;
bool pri[N];
int prime[N],mul[N],phi[N],cnt[N],idx;
inline void sieve(int x){
    mul[1]=1;
    phi[1]=1;
    memset(pri,true,sizeof pri);
    for(int i=2;i<=x;i++){
        if(pri[i]) prime[++idx]=i,mul[i]=-1,phi[i]=i-1,cnt[i]=1;
        for(int j=1;j<=idx&&prime[j]*i<=x;j++){
            pri[i*prime[j]]=false;
            if(i%prime[j]) mul[i*prime[j]]=-mul[i],phi[i*prime[j]]=phi[i]*(prime[j]-1),cnt[i*prime[j]]=cnt[i]+1;
            else{mul[i*prime[j]]=0,phi[i*prime[j]]=phi[i]*prime[j],cnt[i*prime[j]]=cnt[i];break;}
        }
    }
}

狄利克雷卷积

存在算术函数 ff 和 gg，其狄利克雷卷积记为 f∗gf*g，满足： (f∗g)(n)=∑d∣nf(d)×g(nd)(f*g)(n)=\sum_{d|n}f(d)\times g(\frac{n}{d}) 或 (f∗g)(n)=∑ab=nf(a)×g(b)(f*g)(n)=\sum_{ab=n}f(a)\times g(b)
两种情况本质上是一致的，只是两种不同的写法。
这里给出几对常见的 f,gf,g：
  1. μ∗I=ϵ\mu*I=\epsilon 源于 ∑d∣nμ(d)=[n=1]\sum\limits_{d|n} \mu(d)=[n=1]
  2. φ∗I=id\varphi*I=id 源于 ∑d∣nφ(d)=n\sum\limits_{d|n}\varphi(d)=n
  3. μ∗id=φ\mu*id=\varphi 源于 φ(n)=∑i=1n[gcd(i,n)=1]=∑d∣nndμ(d)\varphi(n)=\sum\limits_{i=1}^n [gcd(i,n)=1]=\sum\limits_{d|n}\frac{n}{d}\mu(d)
  4. I∗id=σI*id=\sigma
其中 I(x)=1,ϵ(x)=[x=1],id(x)=xI(x)=1,\epsilon(x)=[x=1],id(x)=x。

整除分块

对于 ⌊nl⌋\lfloor \frac{n}{l}\rfloor 明显存在一个区间 [l,r][l,r] 使得 ∀i∈[l,r],⌊ni⌋=⌊nl⌋\forall i\in[l,r],\lfloor \frac{n}{i}\rfloor=\lfloor \frac{n}{l}\rfloor，若给定 ll，rr 的最大值是 ⌊n⌊nl⌋⌋\lfloor\frac{n}{\lfloor\frac{n}{l}\rfloor}\rfloor，如果将 ⌊ni⌋\lfloor \frac{n}{i}\rfloor 值相同的 ii 分为一个块，块的数量小于 2n2\sqrt{n}，可以大大优化形似 ∑i=1nf(i)×g(⌊ni⌋)\sum\limits_{i=1}^n f(i)\times g(\lfloor\frac{n}{i}\rfloor) 求和公式计算的时间复杂度，详见例题。

杜教筛

杜教筛是一种用于求数论函数前缀和的非线性算法，可以在 O(n23)O(n^{\frac{2}{3}}) 的时间复杂度内求出 S(n)=∑i=1nf(i)S(n)=\sum\limits_{i=1}^{n} f(i) 的值。
为了快速求 f(x)f(x) 的前缀和，我们可以为它找到一个函数 g(x)g(x) 使得 h(x)=(f∗g)(x)h(x)=(f*g)(x) 与 g(x)g(x) 的前缀和是好求的，这时就可以用狄利克雷卷积对式子进行一些变换了： ∑i=1nh(i)=∑i=1n∑d∣ig(d)f(nd)=∑d=1ng(d)∑d∣inf(id)=∑d=1ng(d)∑i=1⌊nd⌋f(i)=∑d=1ng(d)S(⌊nd⌋)\begin{aligned}\sum\limits_{i=1}^{n}h(i)&=\sum\limits_{i=1}^{n}\sum_{d|i}g(d)f(\frac{n}{d})\\&=\sum\limits_{d=1}^{n}g(d)\sum\limits_{d|i}^nf(\frac{i}{d})\\&=\sum\limits_{d=1}^{n}g(d)\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}f(i)\\&=\sum\limits_{d=1}^{n}g(d)S(\lfloor\frac{n}{d}\rfloor)\end{aligned}
其中记 S(x)=∑i=1xf(i)S(x)=\sum\limits_{i=1}^{x}f(i)
于是我们可以得到： ∑i=1nh(i)=∑d=1ng(d)S(⌊nd⌋)\sum\limits_{i=1}^{n}h(i)=\sum\limits_{d=1}^{n}g(d)S(\lfloor\frac{n}{d}\rfloor) ∑i=1nh(i)=g(1)S(n)+∑d=2ng(d)S(⌊nd⌋)\sum\limits_{i=1}^{n}h(i)=g(1)S(n)+\sum\limits_{d=2}^{n}g(d)S(\lfloor\frac{n}{d}\rfloor) g(1)S(n)=∑i=1nh(i)−∑d=2ng(d)S(⌊nd⌋)g(1)S(n)=\sum\limits_{i=1}^{n}h(i)-\sum\limits_{d=2}^{n}g(d)S(\lfloor\frac{n}{d}\rfloor) 根据这个式子我们可以写出如下伪代码：
CPP
long long get_fsum(int x){
    long long res=sumh(x);//h的前缀和
    for(int i=2;i<=x;i=r+1){
        int r=x/(x/i);//整除分块
        res-=(sumg(r)-sumg(i-1))*get_fsum(x/i);
    }
    return res;
}
我们假设 g,hg,h 求前缀和的时间复杂度是 O(1)O(1) 的，那么这样的杜教筛时间复杂度是 O(n34)O(n^{\frac{3}{4}}) 的，证明如下：
设在 xx 时我们计算 S(x)S(x) 附加计算的 S(y),y=⌊xi⌋ i=2,3,...,nS(y),y=\lfloor\frac{x}{i}\rfloor\ i=2,3,...,n 其中 yy 构成的集合为 T(x)={y∣y=⌊xi⌋,i=2,3,...,x}T(x)=\{y|y=\lfloor\frac{x}{i}\rfloor,i=2,3,...,x\}，根据整除分块的结论，我们可以得到 ∀z∈T(x)\forall z\in T(x) 必然有 T(z)⊆T(x)T(z)\subseteq T(x)，我们可以记忆化记录 ∀z∈T(n)\forall z\in T(n) 的 S(z)S(z) 即可，而这样的 zz 个数仅有 n\sqrt{n} 个，计算 S(z)S(z) 的时间复杂度是基于整除分块的 O(z）O(\sqrt{z}） 的，记 T′(n)=T(n)∪{n}T'(n)=T(n)\cup\{n\}，时间复杂度即为： O(∑z∈T′(n)z)O(\sum_{z\in T'(n)}\sqrt{z}) 我们可以将 T′(n)T'(n) 拆为 A={x∣x∈T′(n),x>n}A=\{x|x\in T'(n),x>\sqrt{n}\} 与 B={x∣x∈T′(n),x≤n}B=\{x|x\in T'(n),x\le\sqrt{n}\}
对于 AA 部分： ∑z∈Az≈∑i=1nni=n∑i=1n1i\sum_{z\in A}\sqrt{z}\approx\sum\limits_{i=1}^{\sqrt{n}}\sqrt{\frac{n}{i}}=\sqrt{n}\sum\limits_{i=1}^{\sqrt{n}}\sqrt{\frac{1}{i}} 已知 ∑i=1k1i∼2k\sum\limits_{i=1}^{k}\sqrt{\frac{1}{i}}\sim2\sqrt{k}，所以： ∑z∈Az≈n⋅2n=2n34\sum_{z\in A}\sqrt{z}\approx\sqrt{n}\cdot2\sqrt{\sqrt{n}}=2n^{\frac{3}{4}} 对于 BB 部分 ∑z∈Bz=∫1nz dz=23z32∣1n\sum_{z\in B}\sqrt{z}=\int_{1}^{\sqrt{n}}\sqrt{z}\ dz=\left.\frac{2}{3}z^{\frac{3}{2}}\right|_1^{\sqrt{n}} 分别带入上下界得： ∑z∈Bz=23z32∣1n=23(z34−1)\sum_{z\in B}\sqrt{z}=\left.\frac{2}{3}z^{\frac{3}{2}}\right|_1^{\sqrt{n}}=\frac{2}{3}(z^{\frac{3}{4}}-1) 于是总时间复杂度为： O(∑z∈T′(n)z)=O(2n34+23(z34−1))=O(n34)O(\sum_{z\in T'(n)}\sqrt{z})=O(2n^{\frac{3}{4}}+\frac{2}{3}(z^{\frac{3}{4}}-1))=O(n^{\frac{3}{4}}) 我们还可以继续优化杜教筛，我们先用线性筛筛出 i≤n23i\le n^{\frac{2}{3}} 的 S(i)S(i)，此时线性筛与杜教筛的时间复杂度均为 O(n23)O(n^{\frac{2}{3}})，达到最优，证明过程与上面类似。

实际应用

接下来我们回归题目，对于求 μ\mu 的前缀和就可以用前置知识中给出的 μ∗I=ϵ\mu*I=\epsilon，这非常容易实现。同理求 φ\varphi 的前缀和就可以用 φ∗I=id\varphi*I=id，依旧容易实现，接下来给出代码。

CODE

CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long 
int t,pri[1000005],prime[1000005],idx,mul[1000005],phi[1000005];
unordered_map<int,int>mull,phii,book_mul,book_phi;
const int len=1000000;
void init(){
    mul[1]=1;
    phi[1]=1;
    memset(pri,true,sizeof pri);
    for(int i=2;i<=len;i++){
        if(pri[i]) {prime[++idx]=i;mul[i]=-1;phi[i]=i-1;}
        for(int j=1;j<=idx&&i*prime[j]<=len;j++){
            pri[i*prime[j]]=false;
            if(i%prime[j]){mul[i*prime[j]]=-mul[i];phi[i*prime[j]]=phi[i]*(prime[j]-1);}
            else{mul[i*prime[j]]=0;phi[i*prime[j]]=phi[i]*prime[j];break;}
        }
    }
    for(int i=1;i<=len;i++)mul[i]+=mul[i-1],phi[i]+=phi[i-1];
}
int get_mul(int x){
    if(x<=len)return mul[x];
    else if(book_mul[x]) return mull[x];
    int r,res=1;
    for(int i=2;i<=x;i=r+1){
        r=x/(x/i);
        res-=(r-i+1)*get_mul(x/i);
    }
    book_mul[x]=1,mull[x]=res;
    return res;
}
int get_phi(int x){
    if(x<=len)return phi[x];
    else if(book_phi[x]) return phii[x];
    int r,res=(x+1)*x/2;
    for(int i=2;i<=x;i=r+1){
        r=x/(x/i);
        res-=(r-i+1)*get_phi(x/i);
    }
    book_phi[x]=1,phii[x]=res;
    return res;
}
signed main(){
    init();
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        cout<<get_phi(n)<<" "<<get_mul(n)<<endl;
    }
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...