莫比乌斯反演 整理

莫比乌斯反演略解

Posted by Dispwnl on June 15, 2018

最近在肝莫比乌斯反演…推式子好难啊QAQ

莫比乌斯函数

最基础的莫比乌斯函数$\mu$：

  • 性质

这个函数满足以下性质：

$\mu$满足一些性质：

  1. $\sum_{d\vert n} \mu(d)=[n==1]$这个推式子时用的很多

  2. $\sum_{d\vert n}\frac{\mu(d)}{d}=\frac{\varphi(n)}{n}$

  • 筛函数

可以欧拉筛$O(n)$求出$\mu$

代码：

u[1]=1;
for(int i=2;i<=n;++i)
  {
  	if(!use[i]) pm[++tot]=i,u[i]=-1;
  	for(int j=1;j<=tot&&pm[j]*i<=n;++j)
  	  {
  	  	use[pm[j]*i]=1;
  	  	if(i%pm[j]==0) break;
  	  	u[pm[j]*i]=-u[i];
	  }
  }

莫比乌斯反演

然后就是莫比乌斯繁衍反演啦

假设有定义域为非负整数集合的两个函数$F(n)$，$f(n)$，并且$F(n)=\sum_{d\vert n}f(d)$

则有：$f(n)=\sum_{d\vert n}\mu(d)F(\frac{n}{d})$

  • 证明

$\sum_{d\vert n}\mu(d)F(\frac{n}{d})=\sum_{d\vert n}\mu(d)\sum_{x\vert \frac{n}{d}}f(x)$

$=\sum_{x\vert n}f(x)\sum_{d\vert \frac{n}{x}}\mu(d)$

$=\sum_{x\vert n}f(x)[n==x]$

$=f(n)$（最后根据的是μ函数的性质）

当$F(n)=\sum_{n\vert d}f(d)$

则有：$f(n)=\sum_{n\vert d}\mu(\frac{d}{n})F(d)$

这就是莫比乌斯反演的基本内容了

  • 常见处理

加一些常见的处理（前方大堆公式高能预警）：

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

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

$F(x)=\sum_{x\vert d}f(d)$

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

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

$=\sum_{i=1}^{\left\lfloor\frac{n}{x}\right\rfloor}\sum_{i=1}^{\left\lfloor\frac{m}{x}\right\rfloor}[1\vert\gcd(i,j)]$

$=\left\lfloor\frac{n}{x}\right\rfloor\left\lfloor\frac{m}{x}\right\rfloor​$

$f(x)=\sum_{x\vert d}\mu(\frac{d}{x})F(d)$

$=\sum_{x\vert d}\mu(\frac{d}{x})\left\lfloor\frac{n}{d}\right\rfloor\left\lfloor\frac{m}{d}\right\rfloor$

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

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

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

后面部分就是上一个的处理，可得：$\sum_{d=1}^{min(n,m)}d\sum_{i=1}^{min(\left\lfloor\frac{n}{d}\right\rfloor,\left\lfloor\frac{m}{d}\right\rfloor)}\mu(i)\left\lfloor\frac{n}{id}\right\rfloor\left\lfloor\frac{m}{id}\right\rfloor$

设$T=id$，提出来：$\sum_{T=1}^{min(n,m)}\left\lfloor\frac{n}{T}\right\rfloor\left\lfloor\frac{m}{T}\right\rfloor\sum_{d\vert T}\mu(\frac{T}{d})d$

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

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

$F(x)=\sum_{x\vert d}f(d)$

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

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

$=x^2\sum_{i=1}^{\left\lfloor\frac{n}{x}\right\rfloor}\sum_{i=1}^{\left\lfloor\frac{m}{x}\right\rfloor}[1\vert\gcd(i,j)]ij$

$=x^2\sum_{i=1}^{\left\lfloor\frac{n}{x}\right\rfloor}\sum_{i=1}^{\left\lfloor\frac{m}{x}\right\rfloor}ij$

$f(x)=\sum_{x\vert d}\mu(\frac{d}{x})F(d)$

$=\sum_{x\vert d}d^2\mu(\frac{d}{x})\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum_{i=1}^{\left\lfloor\frac{m}{d}\right\rfloor}ij$

$=\sum_{x\vert d}d^2\mu(\frac{d}{x})\frac{\left\lfloor\frac{n}{d}\right\rfloor\left\lfloor\frac{m}{d}\right\rfloor(\left\lfloor\frac{n}{d}\right\rfloor+1)(\left\lfloor\frac{m}{d}\right\rfloor+1)}{4}$

$=x^2\sum_{i=1}^{min(\left\lfloor\frac{n}{x}\right\rfloor,\left\lfloor\frac{m}{x}\right\rfloor)}i^2\mu(i)\frac{\left\lfloor\frac{n}{ix}\right\rfloor\left\lfloor\frac{m}{ix}\right\rfloor(\left\lfloor\frac{n}{ix}\right\rfloor+1)(\left\lfloor\frac{m}{ix}\right\rfloor+1)}{4}$

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

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

后面部分就是上一个的处理，可得：$\sum_{d=1}^{min(n,m)}d^3\sum_{i=1}^{min(\left\lfloor\frac{n}{d}\right\rfloor,\left\lfloor\frac{m}{d}\right\rfloor)}i^2\mu(i)\frac{\left\lfloor\frac{n}{id}\right\rfloor\left\lfloor\frac{m}{id}\right\rfloor(\left\lfloor\frac{n}{id}\right\rfloor+1)(\left\lfloor\frac{m}{id}\right\rfloor+1)}{4}$

设$T=id$，提出来：$\sum_{T=1}^{min(n,m)}\frac{\left\lfloor\frac{n}{T}\right\rfloor\left\lfloor\frac{m}{T}\right\rfloor(\left\lfloor\frac{n}{T}\right\rfloor+1)(\left\lfloor\frac{m}{T}\right\rfloor+1)}{4}T^2\sum_{d\vert T}\mu(\frac{T}{d})d$

MUSIC
    FRIENDS