莫比乌斯反演与杜教筛

发表于 2018-12-30 更新于 2022-02-14 分类于学习笔记

$\ \ \ \ \ \ \ \,$关于莫比乌斯反演，杜教筛等的杂记：

初识数论常见积性函数：欧拉函数$\varphi$，莫比乌斯函数$\mu$

$\ \ \ \ \ \,$所谓积性函数，就是对于一个函数$f(x)$，若是对于任意$x_1$，$x_2$满足$f(x_1)\times f(x_2)=f(x_1\times x_2)$。对于任何积性函数$f(x)$，都有$f(1)=1$。

欧拉函数$\varphi(x)$的意义：在$[1,x]$内，与$x$互质的个数。

$1$.若$x$为素数，$\varphi(x)=x-1$;

$2$.若$x\%p=0$，$\varphi(x\cdot p)=\varphi(x)\cdot p$;

$3$.若$x\%p\neq 0$，且$x$为素数，$\varphi(x\cdot p)=\varphi(x)\cdot (p-1)$;

【证明戳这里~~（%%%大巨佬orz）~~】
莫比乌斯函数$\mu(x)$的意义：设$x$的不同质因子个数为$a$，$\mu(x)=(-1)^{a}$；当n存在平方因子时，$\mu(x)=0$。

$1$.若$x$有奇数个不同质因数，$\mu(x)=-1$。

$2$.若$x$有偶数个不同质因数，$\mu(x)=1$。

$3$.若$x$有平方因子，$\mu(x)=0$。

$\ \ \ \ \ \,$还有一些简单的积性函数，在这里一并介绍了：

$ϵ(x)=\begin{cases}1&x=1\\0&x>1\end{cases}$

$id(x)=x$

$id^k(x)=x^k$

$\sigma(x)=\sum_{i|x}1$

$1$

数论分块

$\ \ \ \ \ \,$很多时候，我们会遇到这样的式子:

$\sum_{i=1}^{n}f(i)\times g\left(\left\lfloor\frac{n}{i}\right\rfloor\right)$

$\ \ \ \ \ \,$若是我们已经提前知道了$f(x)$在$x\in [1,n]$的值了，但是需要多次计算上面形式的式子的值，每次询问复杂度是$O(n)$的，显然在询问很多的时候，没有很划算。

$\ \ \ \ \ \,$我们枚举了很多$i$，使得很多$\left\lfloor\frac{n}{i}\right\rfloor$都相等，所以我们可以把$\sum_{i=1}^{n}$，分成$\sqrt{n}\ $块，使得每一块的$\left\lfloor\frac{n}{i}\right\rfloor$都相等，这样我们可以通过结合律得到下面的式子，$O(n)$预处理$sum(x)=\sum_{i=1}^{x}f(i)$，来简化询问复杂度到$O(\sqrt{n})$：

int Get_ans(int n){
  long long ans=0;
  for(int l=1,r;l<=n;l=r+1){
    r=n/(n/l);
    ans+=g(n/l)*(sum[r]-sum[l-1]);
  }
  return ans;
}

狄利克雷卷积

$(f*g)(n)=\sum_{x|n}f(x)\times g\left(\frac{n}{x}\right)$

既：

$(f*g)(n)=\sum_{xy=n}f(x)\times g(y)$

狄利克雷卷积的性质：

**1.交换律:** $f*g=g*f$；

**2.结合律:**  $(f*g)*h=g*(f*h)$；$(a\times f)*g=a\times (f*g)$；

**3.分配律:**  $(f+g)*h=f*h+g*h$；

**4.单位元:**  $ϵ*f=f$；其中$ϵ(x)=\begin{cases}1&x=1\\0&x>1\end{cases}$；

**5.逆元:**  对于每个$f(1)\neq0$的函数，都存在一个函数$g$使得$f*g=ϵ$；

**6.两个积性函数的狄利克雷卷积是积性函数。**

$\ \ \ \ \ \,$如何求一个函数的逆：

$\begin{aligned}ϵ&=f*g\\ &=\sum_{x|n}f(x)\times g\left(\frac{n}{x}\right)\\ &=f(1)\times g(n)+\sum_{x|n,i\neq1}f(x)\times g\left(\frac{n}{x}\right)\\&=[n=1]\end{aligned}$
$\ \ \ \ \ \,$所以有：
$f(1)\times g(n)=[n=1]-\sum_{x|n,i\neq1}f(x)\times g\left(\frac{n}{x}\right)$
$g(n)=\frac{1}{f(1)}\left([n=1]-\sum_{x|n,i\neq1}f(x)\times g\left(\frac{n}{x}\right)\right)$

$\ \ \ \ \ \,$其中$\mu$就是函数$1$的逆，也就是说$\mu*1=ϵ$

莫比乌斯反演

$\ \ \ \ \ \,$莫比乌斯反演的本质就是利用性质$\mu*1=ϵ$，改变枚举方式，降低式子的复杂度。

$\ \ \ \ \ \,$最常见的操作是,反演式子$\sum_{i=1}^n\sum_{j=1}^{m}[gcd(i,j)=1]$:

$\sum_{i=1}^n\sum_{j=1}^{m}[gcd(i,j)=1]$

$\sum_{i=1}^n\sum_{j=1}^{m}ϵ(gcd(i,j))$

$\sum_{i=1}^n\sum_{j=1}^{m}(\mu*1)(gcd(i,j))$

$\sum_{i=1}^n\sum_{j=1}^{m}\sum_{d|gcd(i,j)}\mu(d)\times 1$

$\sum_{i=1}^n\sum_{j=1}^{m}\sum_{d=1}^{min(n,m)}\mu(d)[d|gcd(i,j)]$

$\sum_{d=1}^{min(n,m)}\mu(d)\sum_{i=1}^n\sum_{j=1}^{m}[d|gcd(i,j)]$

$\sum_{d=1}^{min(n,m)}\mu(d)\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{m}{d}\right\rfloor}1$

$\sum_{d=1}^{min(n,m)}\mu(d)\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}1\sum_{j=1}^{\left\lfloor\frac{m}{d}\right\rfloor}1$

$\sum_{d=1}^{min(n,m)}\mu(d){\left\lfloor\frac{n}{d}\right\rfloor}{\left\lfloor\frac{m}{d}\right\rfloor}$

莫比乌斯反演经典例题回顾

P2522 [HAOI2011]Problem b（反演+容斥）

P2257 YY的GCD（反演）

P3312 [SDOI2014]数表（反演+离线+数据结构）

P3704 [SDOI2017]数字表格（反演）

P3327 [SDOI2015]约数个数和（反演，数表的简化版）

P3455 [POI2007]ZAP-Queries（反演，裸的）

P1829 [国家集训队]Crash的数字表格 / JZPTAB（反演+欧拉筛，做法新奇）

P3768 简单的数学题（反演+杜教筛）

P4240 毒瘤之神的考验（反演+奇怪的分块，基本上很结论题了）

P1587 [NOI2016]循环之美（反演+杜教筛+数学知识+奇技淫巧，难题来了）

杜教筛

【铃悬的数学小讲堂——杜教筛】

$\ \ \ \ \ \,$杜教筛是求积性函数的前缀和的筛法，复杂度可以达到小于线性的$O(n^{\frac{2}{3}})$。

$\ \ \ \ \ \,$对于一个积性函数$f$，令$S(n)=\sum_{i=1}^nf(i)$，再新定义一个函数$g$，则有：

$\begin{aligned}&\sum_{i=1}^n(f*g)(i)\\=&\sum_{i=1}^n\sum_{x\times y=i}f(x)\times g(y)\\=&\sum_{y=1}^ng(y)\sum_{x\times y\leq n}f(x)\\=&\sum_{y=1}^ng(y)\sum_{x=1}^{\left\lfloor\frac{n}{y}\right\rfloor}f(x)\\=&\sum_{y=1}^ng(y)S\left(\left\lfloor\frac{n}{y}\right\rfloor\right)\end{aligned}$

$\ \ \ \ \ \,$那么就有：

$\sum_{i=1}^n(f*g)(i)=g(1)S(n)+\sum_{y=2}^ng(y)S\left(\left\lfloor\frac{n}{y}\right\rfloor\right)$

$\ \ \ \ \ \,$既：

$g(1)S(n)=\sum_{i=1}^n(f*g)(i)-\sum_{y=2}^ng(y)S\left(\left\lfloor\frac{n}{y}\right\rfloor\right)$

$S(n)=\frac{\sum_{i=1}^n(f*g)(i)-\sum_{y=2}^ng(y)S\left(\left\lfloor\frac{n}{y}\right\rfloor\right)}{g(1)}$

$S(n)={\sum_{i=1}^n(f*g)(i)-\sum_{y=2}^ng(y)S\left(\left\lfloor\frac{n}{y}\right\rfloor\right)}$

$\ \ \ \ \ \,$若是函数$(f*g)$和$g$的前缀和都可以$O(1)$地算出来，那么我们计算$S(n)$的值的时候递归处理，便可以优化复杂度到$O(n^{\frac{3}{4}})$。

$\ \ \ \ \ \,$但若是我们先线性预处理出$S(i)\ {i\in[1,n^{\frac{2}{3}}]}$的值，复杂度就可以优化到$O(n^{\frac{2}{3}})$

$\ \ \ \ \ \,$那么现在的问题是如何找到这个神奇的函数$g$：

对于$\varphi(x)$：

$\begin{aligned}\varphi(x)=&\prod_{p|x,p\ \rm{is\ prime}}\frac{p^k(p-1)}{p}\\=&x\times \prod_{p|x,p\ \rm{is\ prime}}\left(1-\frac{1}{p}\right)\end{aligned}$

$\begin{aligned}(\varphi*1)(x)=&\sum_{i|x}\varphi(i)\times 1\left(\frac{x}{i}\right)\\=&\sum_{i|x}\varphi(i)\\=&\sum_{i|x}i\times \prod_{p|i,p\ \rm{is\ prime}}\left(1-\frac{1}{p}\right)\end{aligned}$

显然$(\varphi*1)(x)$

在$x$为素数的次方情况下，$(\varphi*1)(x)=x$

，而$(\varphi*1)(x)$

又为积性函数，可以证明在定义域下$(\varphi*1)(x)=x$

，既$\varphi*1=id$。

所以我们选取$g=1$,$(f*g)=id$，容易求和。

long long Sum_id(int x){return 1ll*x*(x+1)/2;}
long long Sum_1(int l,int r){return 1ll*r-l+1;}
long long g1=1ll;
long long Sum_phi(int x){
  long long ret=Sum_id(x);
  for(int i=2,j;i<=x;i=j+1)
  j=x/(x/i),ret-=Sum_1(i,j)*Sum_phi(x/i);
  return ret;
}

对于$\mu(x)$：

已知$\mu*1=ϵ$

所以我们选取$g=1$,$(f*g)=ϵ$，容易求和。

long long Sum_e(int x){return 1ll;}
long long Sum_1(int l,int r){return 1ll*r-l+1;}
long long g1=1ll;
long long Sum_mu(int x){
  long long ret=Sum_e(x);
  for(int i=2,j;i<=x;i=j+1)
  j=x/(x/i),ret-=Sum_1(i,j)*Sum_mu(x/i);
  return ret;
}

注意：杜教筛套杜教筛复杂度还是$O(n^\frac{2}{3})$，因为实际上他们是并列进行的。

贝尔级数

$\ \ \ \ \ \,$对于其他积性函数，为了找到满足条件的$g$，我们引入贝尔级数，需要用到生成函数的姿势，但是实际上只需要记住下面的公式就够用了：

$\ \ \ \ \ \,$对于积性函数$f$，定义$f$模$p$的贝尔级数为：

$f_p(x)=\sum_{i=0}^{\infty}f(p^i)x^i$

$\ \ \ \ \ \,$一个完全积性函数的贝尔级数为几何级数：

$f_p(x)=\frac{1}{1-f(p)\times x}$

$\ \ \ \ \ \,$例如（“*”完全积性函数）:

*$ϵ_p(x)=1$

*$1_p(x)=\frac{1}{1-x}$

*$id^k_p(x)=\frac{1}{1-p^k\cdot x}$

$\mu_p(x)=1-x$

$\sigma_p(x)=\frac{1}{(1-x)^2}$

$(\sigma_1)_p(x)=\frac{1}{1-\sigma_1(p)x+px^2}$ ——> $\left[(\sigma_k)_p(x)=\frac{1}{1-\sigma_k(p)x+p^kx^2}\right]$

$\varphi_p(x)=\frac{1-x}{1-p\cdot x}$

$\ \ \ \ \ \,$有了这个东西，我们边可以把狄利克雷卷积化成一般卷积的形式：

$(f*g)_p(x)=f_p(x)\times g_p(x)$

$\ \ \ \ \ \,$再带回去就可以得到我们想要的$g$和$g*f$，主观感觉非常复杂。

一些比较常见的容易求的卷积

$\mu*\sigma=1$

$id*id=n$

$\varphi*1=id$

$\mu*id=\varphi$