莫比乌斯反演与杜教筛

· · 个人记录

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

- 欧拉函数$\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）~~】](https://www.luogu.org/blog/hdxrie/dui-ou-la-han-shuo-di-li-xie) - 莫比乌斯函数$\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)$预处理${\rm sum}(x)=\sum_{i=1}^{x}f(i)$，来简化询问复杂度到$O(\sqrt{n})$： ```cpp 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; } ``` --- ## - [【积性函数的线性筛】](https://www.luogu.org/blog/Althen-Way-Satan/xian-xing-shai) --- ## - 狄利克雷卷积 $$(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=ϵ

-莫比乌斯反演

$\ \ \ \ \ \ $最常见的操作是,反演式子$\sum_{i=1}^n\sum_{j=1}^{m}[{\rm gcd}(i,j)=1]$: $$\sum_{i=1}^n\sum_{j=1}^{m}[{\rm gcd}(i,j)=1]$$ $$\sum_{i=1}^n\sum_{j=1}^{m}ϵ({\rm gcd}(i,j))$$ $$\sum_{i=1}^n\sum_{j=1}^{m}(\mu*1)({\rm gcd}(i,j))$$ $$\sum_{i=1}^n\sum_{j=1}^{m}\sum_{d|{\rm gcd}(i,j)}\mu(d)\times 1$$ $$\sum_{i=1}^n\sum_{j=1}^{m}\sum_{d=1}^{{\rm min}(n,m)}\mu(d)[d|{\rm gcd}(i,j)]$$ $$\sum_{d=1}^{{\rm min}(n,m)}\mu(d)\sum_{i=1}^n\sum_{j=1}^{m}[d|{\rm gcd}(i,j)]$$ $$\sum_{d=1}^{{\rm 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}^{{\rm 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}^{{\rm min}(n,m)}\mu(d){\left\lfloor\frac{n}{d}\right\rfloor}{\left\lfloor\frac{m}{d}\right\rfloor}$$ ## $\ \ \ \ \ \ $例题 - ## [莫比乌斯反演经典例题回顾（一）](https://www.luogu.org/blog/Althen-Way-Satan/mu-bi-wu-si-fan-yan-jing-dian-li-ti-hui-gu-1) [P2522 [HAOI2011]Problem b](https://www.luogu.org/problemnew/show/P2522)（反演+容斥） [P2257 YY的GCD](https://www.luogu.org/problemnew/show/P2257)（反演） [P3312 [SDOI2014]数表](https://www.luogu.org/problemnew/show/P3312)（反演+离线+数据结构） [P3704 [SDOI2017]数字表格](https://www.luogu.org/problemnew/show/P3704)（反演） - ## [莫比乌斯反演经典例题回顾（二）](https://www.luogu.org/blog/Althen-Way-Satan/mu-bi-wu-si-fan-yan-jing-dian-li-ti-hui-gu-2) [P3327 [SDOI2015]约数个数和](https://www.luogu.org/problemnew/show/P3327)（反演，数表的简化版） [P3455 [POI2007]ZAP-Queries](https://www.luogu.org/problemnew/show/P3455)（反演，裸的） [P1829 [国家集训队]Crash的数字表格 / JZPTAB](https://www.luogu.org/problemnew/show/P1829)（反演+欧拉筛，做法新奇） - ## [莫比乌斯反演经典例题回顾（三）](https://www.luogu.org/blog/Althen-Way-Satan/mu-bi-wu-si-fan-yan-jing-dian-li-ti-hui-gu-3) [P3768 简单的数学题](https://www.luogu.org/problemnew/show/P3768)（反演+杜教筛） [P4240 毒瘤之神的考验](https://www.luogu.org/problemnew/show/P4240)（反演+奇怪的分块，基本上很结论题了） [P1587 [NOI2016]循环之美](https://www.luogu.org/problemnew/show/P1587)（反演+杜教筛+数学知识+奇技淫巧，难题来了） --- ## - 杜教筛 [【铃悬的数学小讲堂——杜教筛】](https://lx-2003.blog.luogu.org/dujiao-sieve#) $\ \ \ \ \ \ $杜教筛是求积性函数的前缀和的筛法，复杂度可以达到小于线性的$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}}) - 对于$\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,$(fg)=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;
}
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;
}