杜教筛模板 / p4213

前言

杜教筛是一个用来快速求积性函数前缀和的方法，其时间复杂度可达到 O ( n 2 3 ) O(n^{\frac{2}{3}}) O(n32​)，进而可以处理1e9的问题，其原理如下： 设 待 求 和 式 为 S ( n ) = ∑ i = 1 n f ( i ) ,   n = 1 e 9 设待求和式为 S(n)= \sum_{i=1}^{n}f(i), \space n=1e9 设待求和式为S(n)=i=1∑n​f(i), n=1e9我们的工作是找一个可在 O ( 1 ) O(1) O(1)时间内查询的积性函数 g g g，那么它与待求和式有如下关系： ∑ i = 1 n ( f ∗ g ) ( i ) = ∑ i = 1 n g ( i ) S ( ⌊ n i ⌋ ) \sum_{i=1}^n(f*g)(i)=\sum_{i=1}^ng(i)S(\lfloor \frac{n}{i} \rfloor) i=1∑n​(f∗g)(i)=i=1∑n​g(i)S(⌊in​⌋) 简证： ∑ i = 1 n ( f ∗ g ) ( i ) \sum_{i=1}^n(f*g)(i) i=1∑n​(f∗g)(i) = ∑ i = 1 n ∑ d ∣ i g ( d ) f ( i d ) =\sum_{i=1}^n\sum_{d|i}g(d)f(\frac{i}{d}) =i=1∑n​d∣i∑​g(d)f(di​) = ∑ i = 1 n ∑ j = 1 ⌊ n i ⌋ g ( i ) f ( j ) =\sum_{i=1}^n\sum_{j=1}^{\lfloor \frac{n}{i} \rfloor}g(i)f(j) =i=1∑n​j=1∑⌊in​⌋​g(i)f(j) = ∑ i = 1 n g ( i ) ∑ j = 1 ⌊ n i ⌋ f ( j ) =\sum_{i=1}^ng(i)\sum_{j=1}^{\lfloor \frac{n}{i} \rfloor}f(j) =i=1∑n​g(i)j=1∑⌊in​⌋​f(j) = ∑ i = 1 n g ( i ) S ( ⌊ n i ⌋ ) =\sum_{i=1}^ng(i)S(\lfloor \frac{n}{i} \rfloor) =i=1∑n​g(i)S(⌊in​⌋)进而可以得到一个方便计算的递推式： g ( 1 ) S ( n ) = ∑ i = 1 n ( f ∗ g ) ( i ) − ∑ i = 2 n g ( i ) S ( ⌊ n i ⌋ ) g(1)S(n)=\sum_{i=1}^n(f*g)(i) - \sum_{i=2}^ng(i)S(\lfloor \frac{n}{i} \rfloor) g(1)S(n)=i=1∑n​(f∗g)(i)−i=2∑n​g(i)S(⌊in​⌋) 我们来分析一下它的时间复杂度，假设我们已预处理过 [ 1 , n ] [1,\sqrt{n}] [1,n ​]，那么 [ 1 , n ] [1,\sqrt{n}] [1,n ​]内的前缀和的前缀和的查询为 O ( t ) O(\sqrt{t}) O(t ​)： O ( S ( n ) ) = O ( 1 ) − O ( ∫ 2 n n x d x ) = O ( n 3 4 ) O(S(n))=O(1)-O(\int_2^{\sqrt{n}}\sqrt{\frac{n}{x}}dx)=O(n^{\frac{3}{4}}) O(S(n))=O(1)−O(∫2n ​​xn​ ​dx)=O(n43​)这个复杂度不错，但我们可以继续改进，预处理 [ 1 , n 2 3 ] [1,n^{\frac{2}{3}}] [1,n32​]的前缀和，则可以得到 O ( n 2 3 ) O(n^{\frac{2}{3}}) O(n32​)的复杂度，证明方法同上 下面给出几个常见的辅助函数： S ( i ) = ∑ i = 1 n μ ( i ) , g ( i ) = I ( i ) S(i)=\sum_{i=1}^{n}\mu(i), g(i)=I(i) S(i)=i=1∑n​μ(i),g(i)=I(i) S ( i ) = ∑ i = 1 n φ ( i ) , g ( i ) = I ( i ) S(i)=\sum_{i=1}^{n}\varphi(i), g(i)=I(i) S(i)=i=1∑n​φ(i),g(i)=I(i) S ( i ) = ∑ i = 1 n i 2 φ ( i ) , g ( i ) = i 2 S(i)=\sum_{i=1}^{n}i^2\varphi(i), g(i)=i^2 S(i)=i=1∑n​i2φ(i),g(i)=i2

一、例题

二、代码及思路 1.思路

直接用 ϕ \phi ϕ 和 μ \mu μ 的板子即可

2.代码

代码如下：

#include 
#include 
#define int long long
using namespace std;
const int maxn = 5e6;
int miu[maxn], phi[maxn];
int premiu[maxn], prephi[maxn];
int prime[maxn], pn;
bool isp[maxn];
map Smiu;
map Sphi;
void table() {
  for (int i = 1; i