筛法
前置知识
数论函数：定义在正整数上的函数。
例：
若 则称 积性。
迪利克雷卷积： 两个数论函数 的迪利克雷卷积为 。满足交换律，结合律。若 积性，则 积性（若完全积性，则没有传递性）。
迪利克雷逆：若 ，则 是 的迪利克雷逆，记 为 。
于是 有迪利克雷逆的充要条件是 。
整除
是最大使 的 。
记 。因此会有整除分块这种优化方式。
莫比乌斯函数 定义为 。
若 含有大于 的平方因子， 。否则，令 为 含有的不同质因子个数，。
由定义，
。（莫比乌斯反演公式）
线性筛可以 求解积性函数。
例1
求
\\&= \sum \limits_{d=1}^n \sigma_1(d)[\sigma_1(d)\le a]\sum \limits_{i=1}^\frac nd\sum\limits_{j=1}^\frac md [\gcd(i,j)=1] \\&= \sum \limits_{d=1}^n \sigma_1(d)[\sigma_1(d)\le a]\sum \limits_{i=1}^\frac nd\sum\limits_{j=1}^\frac md \sum \limits_{k|\gcd(i,j)}\mu(k) \\&= \sum \limits_{d=1}^n \sigma_1(d)[\sigma_1(d)\le a]\sum \limits_{k=1}^\frac nd\lfloor \frac{n}{dk}\rfloor \lfloor \frac{m}{dk} \rfloor \mu(k) \end{align}$$ 设 $T=dk$ $$\begin{align}&= \sum \limits_{T=1}^n \lfloor \frac{n}{T}\rfloor \lfloor \frac{m}{T} \rfloor \sum \limits_{k|T} \mu(k) \sigma_1(\frac Tk) [\sigma_1(\frac Tk)\le a] \end{align}$$ 后面那个式子可以看为一个关于 $(T,a)$ 的函数。考虑预处理 $\sigma_1(x)$ 并将函数值从小到大排序，将询问按照 $a$ 从小到大排序。每次前面的整除分块相当于求一个前缀和询问，我们需要用数据结构维护后面那个东西。树状数组可以。每次 $a$ 变大后，加入一个 $\sigma_1(k)$相当于在 $k,2k,3k,...$ 增加 $\mu(1)\sigma_1(k), \mu(2)\sigma_1(k)...$。最终插入次数调和级数。于是这部分复杂度 $O(n \log^2 n)$。整除分块复杂度 $O(T \sqrt n \log n)$。 ::::info[代码] ```cpp #include<bits/stdc++.h> using namespace std; typedef long long ll; #define int ll const int N=1e5+5,M=(1ll<<31); struct BIT{ int t[N<<1]; int query(int x){ int ret=0; for(;x;x-=(x&-x)){ ret+=t[x];ret%=M; } return ret; } void add(int pos,int x){ for(;pos<N;pos+=(pos&-pos))t[pos]+=x,t[pos]+=M,t[pos]%=M; } }t; pair<int,int> s1[N]; int mu[N],p[N],pcnt; bool isp[N]; void init(){ mu[1]=1; for(int i=2;i<=N-5;i++){ if(!isp[i])p[++pcnt]=i,mu[i]=-1; for(int j=1;j<=pcnt and (i*p[j])<=N-5;j++){ isp[i*p[j]]=1; if(i%p[j]==0){ mu[i*p[j]]=0; break; } mu[i*p[j]]=-mu[i]; } } for(int i=1;i<=N-5;i++){ s1[i].second=i; for(int j=i;j<=N-5;j+=i){ s1[j].first+=i; } } // cerr<<s1[1].first<<" "<<s1[2].first<<" "<<s1[3].first<<" "<<s1[4].first<<endl; sort(s1+1,s1+1+100000); } struct query{ int n,m,a,id; bool operator<(const query &A){return a<A.a;} }q[N]; int ans[N]; int T; signed main(){ cin>>T; init(); for(int i=1;i<=T;i++){ cin>>q[i].n>>q[i].m>>q[i].a;q[i].id=i; if(q[i].n>q[i].m)swap(q[i].n,q[i].m); } sort(q+1,q+1+T);int itr=1; for(int i=1;i<=T;i++){ while(itr<=1e5 and s1[itr].first<=q[i].a){ for(int j=s1[itr].second;j<=N-5;j+=s1[itr].second){ t.add(j,s1[itr].first*mu[j/s1[itr].second]); } itr++; } for(int l=1,r;l<=q[i].n;l=r+1){ r=min(q[i].n/(q[i].n/l),q[i].m/(q[i].m/l)); ans[q[i].id]+=((q[i].n/l)*(q[i].m/l)%M)*(t.query(r)-t.query(l-1))%M; ans[q[i].id]%=M; } } for(int i=1;i<=T;i++)cout<<(ans[i]+M)%M<<endl; return 0; } ``` :::: ### 杜教筛 在一些问题中，我们想对于一个特定的 $n$ 求一个积性函数的前缀和 $\sum \limits_{i=1}^n f(i)$ 。我们想将这个与整除分块相结合。例如，要快速的求 $\sum \limits_{i=1}^n \sum \limits_{j=1}^m [\gcd(i,j)=1]$，我们需要知道所有 $D_n \cup D_m$ 处 $\mu$ 的前缀和。 考虑迪利克雷卷积，设 $h=f*g$，$h$ 的前缀和为 $$\sum \limits_{i=1}^n h(i)=\sum \limits_{i=1}^n \sum \limits_{j|i} f(j)g(\frac ji)=\sum \limits_{i=1}^n\sum \limits_{j=1}^{[\frac ni]} f(i)g(j)\\=\sum \limits_{i=1}^nf(i)G([\frac ni])$$ 于是 $G(i)=\sum \limits_{i=1}^n h(i)-\sum \limits_{i=2}^n f(i)G([\frac ni])$ 。 通过这个式子可以递归计算 $g$ 的前缀和（在 $n$ 的整除点处），要求能快速计算 $f,h$ 的前缀和。 进行优化后（线性筛计算前 $n^{\frac 23}$ 个函数值，然后杜教筛剩下的）可以做到 $O(n^{\frac 23})$ 。 ### $\text{Powerful Number}$ 筛 杜教筛求解 $f$ 的前缀和需要 $\exist g,h, f*g^{-1}=h$ 且 $g,h$ 前缀和易求，对积性函数要求较高，部分函数可能难以使用杜教筛，这时候可以使用PN筛。 设 $n=p_1^{k_1} p_2^{k_2}\cdots p_m^{k_m}$，则 $n$ 是一个 $\text{powerful number}$ 当且仅当 $\forall i,k_i\ge 2$。所有 $\text{powerful number}$ 都可以表示成 $a^2 b^3$ 的形式。 $n$ 以内的 $\text{powerful number}$ 个数是 $O(\sqrt n)$ 的。 假设我们想要求解 $f$ 的前缀和，但 $f$ 不满足杜教筛的条件，此时我们想要找满足杜教筛条件的 $g$，并且对于任意质数 $p$ 满足 $f(p)=g(p)$，则我们有 $h=f*g^{-1}$，$h(1)g(p)+h(p)g(1)=g(p)+h(p)=f(p)+h(p)=f(p)$，$h(p)=0$，所以仅当 $n$ 是 $\text{powerful number}$ 时 $h(n)$ 才有可能非 $0$。 $f=h*g,f$ 的前缀和可以表示为： $\sum \limits_{i=1}^n f(i)=\sum \limits_{i=1}^n \sum \limits_{j=1}^{[\frac{n}{i}]} h(i)g(j)=\sum \limits_{i=1}^nh(i) \sum \limits_{j=1}^{[\frac ni]}g(j)$，可以杜教筛 $g$，在每个 $\text{powerful number}$ 处求解 $h$，即可优化复杂度。考虑计算 $h(p^c)$，一种方式是 $f=g*h\Rightarrow h(p^c)=f(p^c)-\sum \limits_{i=1}^c g(p^i)h(p^{c-i})$，然后进行枚举（根据 $O(\sqrt n)$ 内素数个数为 $O(\frac{n}{\ln n})$，每个素数的指数至多为 $\ln n$，于是这一部分时间复杂度为 $O(\sqrt n\ln n)$）最后搜索 $n$ 以内的 $\text{powerful number}$ 即可。 例：[LOJ #6053. 简单的函数](https://loj.ac/p/6053) 积性函数 $f(n)$ 满足 $f(p^c)=p \operatorname{xor} c$，求 $f$ 的前缀和。$n \le 10^{10}$。 $f(p)=\begin{cases}p+1& (p=2)\\p-1 &\text{otherwise} \end{cases}$，故可以构造 $g(n)=\begin{cases}3\varphi(n) & 2|n \\\varphi(n) &\text{otherwise} \end{cases}$ $g$ 为积性函数。 $$\begin{align} G(n)&=\sum \limits_{i=1}^n [i\bmod 2=1]\varphi(i) +3\sum \limits_{i=1}^n [i\bmod2=0]\varphi(i) \\ &=\sum \limits_{i=1}^n \varphi(i) +2\sum \limits_{i=1}^\frac n2 \varphi(2i) \end{align}$$ 记 $S_1(n)=\sum\limits_{i=1}^n \varphi(i),S_2(n)=\sum \limits_{i=1}^n \varphi(2i)$，$G(n)=S_1(n)+2S_2(\frac n2)$。 当 $2|n$ 时， $$\begin{align}S_2(n)&= \sum \limits_{i=1}^n \varphi(2i)\\&= \sum \limits_{i=1}^\frac n2 (\varphi(2(2i-1)))+\varphi(2(2i)) \\ &=\sum \limits_{i=1}^{\frac n2} \varphi(2i-1)+2\varphi(2i) \ \ ^{[1]} \\ &=S_1(n)+S_2(\frac n2)\end{align}$$ 否则， $\varphi(2n)=\varphi (n)$，$S_2(n)=S_1(n-1)+S_2(\frac n2)+\varphi(n)=S_1(n)+S_2([\frac n2])$。 $S_1$ 可以杜教筛。于是我们可以快速求 $g$ 的前缀和。 然后用 $h(p^c)=f(p^c)-\sum \limits_{i=1}^c g(p^i)h(p^{c-i})$ 可以计算 $h$ 的前缀和。 $\sum \limits_{i=1}^n f(i)=\sum \limits_{i=1}^n \sum \limits_{j=1}^{[\frac{n}{i}]} h(i)g(j)=\sum \limits_{i=1}^nh(i) \sum \limits_{j=1}^{[\frac ni]}g(j)$ $[1]:$ 根据 $\varphi(n)= n\prod\limits_{i=1}^k \frac{p_k-1}{p_k}$ ( $p_k$ 为 $n$ 的不同质因数) 推导可得。 [代码](https://loj.ac/s/2367328) ## Min25筛 Min25筛可以在 $O(\frac{n^{\frac{3}{4}}}{\log n})$ 的复杂度内求一个积性函数 $f(p)$ 的前缀和，要求 $f(p)$ 为关于 $p$ 的简单多项式，且 $f(p^c)$ 可以快速计算。 我们对这个 $f(p)$ 的前缀和每一项按照素数和合数（和1）进行分类： $$\sum\limits_{1\le i\le n}f(i)=\sum \limits_{p\in prime,p\le n}f(p)+\sum \limits_{i \notin prime,i\le n}f(i)$$ 枚举每个合数的最小质因子及次数： $$\sum \limits_{p\in prime,p\le n}f(p)+\sum \limits_{1\le p^k,1\le p\le \sqrt n}f(p^k) \sum \limits_{1\le i\le [\frac{n}{p^k}],\operatorname{lp}(i)>p}f(i)$$ 其中 $\operatorname{lp}(x)$ 代表 $x$ 的最小质因子。 我们分成两步算上面这个式子。 ### 1.求 $\sum \limits_{p\in prime,p\le n}f(p)$ 记 $$g(n,j)=\sum \limits_{(i\in prime \ or \ \operatorname{lp}(i)>p_j) and \ i\le n} i^k$$ $i^k$ 为上文中“简单多项式”的一项（相当于把函数拆开来）。 当 $p_j^2>n$ 时，最小的满足 $\operatorname{lp}(x)=p_j$ 的数为 $p_j^2>n$，不会有贡献。 否则，考虑从 $g(n,j-1)$ 转移到 $g(n,j)$。这个转移的过程中剔除了最小质因子为 $p_j$ 且不满足条件的数的贡献，即： $$g(n,j)=g(n,j-1)-p_j^k[g(\lfloor\frac{n}{p_j}\rfloor,j-1)-g(p_{j-1},j-1)]$$ 关于 $p_j^k[g(\lfloor\frac{n}{p_j}\rfloor,j-1)-g(p_{j-1},j-1)]$： 这是最小质因子恰为 $p_j$ 的合数的贡献。这些合数可以表示为 $p_j\times x$，其中 $x$ 满足 $\operatorname{lp}(x)\ge p_j$。如何计算 $\sum x^k$？ - $g(\lfloor\frac{n}{p_j}\rfloor,j-1)$ 是所有素数或最小质因子大于 $p_{j-1}$ 的数的 $k$ 次方和。这恰好包含了所有 $x$ 和所有小于 $p_j$ 的素数（不需要这一部分，因为 $p_j$ 乘后者的最小质因子是后者自身）。因此要减去后者的贡献，即 $g(p_{j-1},j-1)$。（$=g(p_j-1,j-1)$，因为没有小于 $p_j$ 的合数的最小质因子大于 $p_{j-1}$，只包括了素数的贡献）。 所以我们有了 $g$ 的递推式： $$g(n,j)=\left\{\begin{array}{l}g(n,j-1)& p_j^2>n\\g(n,j-1)-p_j^k[g([\frac{n}{p_j}],j-1)-g(p_j-1,j-1)] & p_j^2\leq n \end{array}\right.$$ $g(p_j-1,j-1)$ 就是 $\sum \limits_{i=1}^{j-1}p_i^k$，$j\le O(\frac{\sqrt n}{\ln n})$，可以直接线性筛。 同时根据整除点的性质（$|D_n|=O(\sqrt n)$），只需处理所有 $[\frac{n}{p_j}]$ 位置的 $g$。 在这一步之后，将 $g(n,j)$ 线性组合为 $\sum \limits_{(i\in prime \ or \ \operatorname{lp}(i)>p_j) and \ i\le n} f(i)$。 ### 2.求后面一部分 记 $$S(n,j)=\sum \limits_{2\le i\le n,\operatorname{lp}(i)>p_j}f(i)$$ 则我们的答案就是 $S(n,0)$。 可以将上式中满足条件的数分为两个部分： - 大于 $p_j$ 的素数： $g(n,x)-g(p_j-1,j-1)$（其中 $x$ 是满足 $p_x^2\le n$ 的最大的 $x$） - 大于 $p_j$ 的合数：枚举最小质因子，有 $\sum \limits_{p_k^e,k>j}f(p_k^e)(S([\frac{n}{p_k^e}],k)+[e\neq 1])$ 所以有 $$S(n,j)=g(n,x)-g(p_j-1,j-1)+\sum_{p_k^e,k>j}f(p_k^e)(S([\frac{n}{p_k^e}],k)+[e\neq 1])$$ 考虑直接爆搜。另外注意到上式不包含 $f(1)$，直接加上即可。 例题： [SP34096 DIVCNTK](https://www.luogu.com.cn/problem/SP34096) 求 $\sum \limits_{i=1}^n \sigma_0(i^k)$。 不难发现 $f(1)=1,f(p)=k+1,f(p^e)=ke+1,f(ab)=f(a)f(b)$（$\gcd(a,b)=1$）。 直接做即可。 ::::info[代码] ```cpp #include<bits/stdc++.h> using namespace std; typedef long long ll; #define int unsigned long long//对 2^64取模 const int N=1e7+5; int p[N],pcnt; bool isp[N]; void init(int n){ // p[0]=1; for(int i=2;i<=n;i++){ if(!isp[i]){ p[++pcnt]=i; // cout<<i<<endl; } for(int j=1;j<=pcnt and i*p[j]<=n;j++){ isp[i*p[j]]=1; if(i%p[j]==0)break; } } } int T,n,k,sqn; int g[N];//g[i] g(第i个整除点,j)的值(其中j被压维) int d[N],ptr;//整除点 int pos[3][N];//d[x]的索引位置,pos[1][x]是小的（n/i）的位置 //,pos[2][x]是大的(n/i)的位置（存的是 x=n/(n/i)） int S(int x,int y){ //S(n,j) if(p[y]>x)return 0; int posx; if(x<=sqn)posx=pos[1][x]; else posx=pos[2][n/x]; int ans=g[posx]-y*(k+1);//y*(k+1)=g(p_y-1,y-1) for(int i=y+1,tmp;i<=pcnt and p[i]*p[i]<=x;i++){ tmp=p[i]; for(int e=1;tmp<=x;e++,tmp*=p[i]){ //枚举p_i^e ans+=(k*e+1)*S(x/tmp,i); if(e>1)ans+=k*e+1; } } return ans; } signed main(){ cin>>T; while(T--){ pcnt=0; cin>>n>>k; sqn=sqrt(n); init(sqn);ptr=0; for(int i=1;i<=n;i=n/(n/i)+1){ d[++ptr]=n/i; g[ptr]=n/i-1;//g(n/i,0)=n/i-1（不包含f(1)） if(n/i<=sqn)pos[1][n/i]=ptr; else pos[2][n/(n/i)]=ptr; } for(int i=1;i<=pcnt;i++){ // cerr<<pcnt<<" "<<ptr<<" "<<p[i]<<" "<<d[1]<<endl; for(int j=1;j<=ptr and p[i]*p[i]<=d[j];j++){ //计算g(d[j],i) int itr; if(d[j]/p[i]<=sqn)itr=pos[1][d[j]/p[i]]; else itr=pos[2][n/(d[j]/p[i])]; // cout<<i<<" "<<j<<" "<<itr<<endl; g[j]-=g[itr]-(i-1);//f(p)=k+1,多项式和p无关（相当于0次项），不用乘p的幂 } } for(int i=1;i<=ptr;i++)g[i]*=(k+1);//f(p)=k+1，现在 g[x]=g(第x个整除点，n)=【<=第x个整除点的f(p)和】 // cerr<<g[1]<<" "<<g[2]<<" "<<g[3]<<" "<<g[4]<<endl; cout<<S(n,0)+1<<endl; } return 0; } ``` :::: [LOJ #6202 叶氏筛法](https://loj.ac/p/6202) $f(p)=p$。只需要第一部分。 [LOJ #572 Misaka Network 与求和](https://loj.ac/p/572)