省选-数学-莫比乌斯反演

推式子。

莫比乌斯函数

$\mu$ 为莫比乌斯函数，定义为

预处理可以用线性筛。

void init(){
	mu[1]=1;
	for(int i=2;i<=50000;i++){
		if(!hs[i]){
			pri[++cnt]=i;
			mu[i]=-1;
		}
		for(int j=1;j<=cnt&&pri[j]*i<=50000;j++){
			hs[pri[j]*i]=1;
			if(i%pri[j]==0){
				mu[i*pri[j]]=0;
				break;
			}
			mu[i*pri[j]]=-mu[i];
		}
	} 
}

这个函数还有一个很神奇的用法，就是 $\mu(x)^2$ 可以表示这个数是否含有平方因子。

性质

常见技巧

$\sum\limits_{d=1}^n d^k\sum\limits_{x=1}^{\lfloor\frac{n}{d}\rfloor}\mu(x)\lfloor\dfrac{n}{dx}\rfloor\lfloor\dfrac{n}{dx}\rfloor$

然后我们令 $T=dx$：

$\sum\limits_{T=1}^n\lfloor\dfrac{n}{T}\rfloor\lfloor\dfrac{m}{T}\rfloor\sum\limits_{d|T}d^k\mu(\dfrac{T}{d})$

莫比乌斯反演

如果：$f(n)=\sum_{d\mid n}g(d)$。

那么：$g(n)=\sum_{d\mid n}\mu(d)f(\frac{n}{d})$。

还有另一种更常用形式，枚举倍数：

若果：$f(n)=\sum_{n|d}g(d)$

那么：$g(n)=\sum_{n|d}\mu(\frac{d}{n})f(d)$

很多时候，我们发现题目中一个函数好求，一个不好求，那么我们可以考虑用好求的那个表示出那个不好求的。

推论

$d(ij)=\sum\limits_{x\mid i}\sum\limits_{y\mid j} [\gcd(x,y)=1]$

来自 P3327 [SDOI2015] 约数个数和。

我们考虑证明，我们发现最困难的是很难保证不计算重复。

我们用一个比较人类智慧的想法：对于每一个 $p^k$，令 $i$ 中有 $p^a$：

• 如果 $k\le a$，那么 $i$ 中有 $p^k$ 则表示这个因数有 $p^k$。
• 如果 $k>a$，$j$ 中有 $p^{k-a}$ 则表示这个因数有 $p^k$。

P2522 [HAOI2011] Problem b

P2522 [HAOI2011] Problem b。

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

$F(n)=\sum_{n|d}f(d)=\lfloor\frac{a}{n}\rfloor\lfloor\frac{b}{n}\rfloor$

用莫比乌斯反演再推回 $f$。

再加上整除分块就行了。

int calc(int n,int m,int k){
	int res=0;
	for(int l=1,r;l<=min(n/k,m/k);l=r+1){
		r=min((n/k)/(int)(n/l/k),(m/k)/(int)(m/l/k));
		res+=(sum[r]-sum[l-1])*(n/l/k)*(m/l/k);
	}
	return res;
}

P3327 [SDOI2015] 约数个数和

P3327 [SDOI2015] 约数个数和。

$\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits_{x\mid i}\sum\limits_{y\mid j} [\gcd(x,y)=1]$

另一种形式

我们直接利用下面的式子带进去做：

常见技巧：

$\sum\limits_{d=1}^n d^k\sum\limits_{x=1}^{\lfloor\frac{n}{d}\rfloor}\mu(x)\lfloor\dfrac{n}{dx}\rfloor\lfloor\dfrac{n}{dx}\rfloor$

然后我们令 $T=dx$：

$\sum\limits_{T=1}^n\lfloor\dfrac{n}{T}\rfloor\lfloor\dfrac{m}{T}\rfloor\sum\limits_{d|T}d^k\mu(\dfrac{T}{d})$

P3704 [SDOI2017] 数字表格

P3704 [SDOI2017] 数字表格。

实在不想打 Latex 了，那就 ctj 吧。

$\begin{aligned}&=\prod_{i=1}^{N}\prod_{j=1}^{M}F_{\gcd(i,j)} \\ &=\prod_{k=1}^{N}{F_{k}}^{\left(\sum_{i=1}^{N}\;\sum_{j=1}^{M}\;\left[\gcd(i,j)=k\right]\right)}\end{aligned}$

$\begin{aligned}&= \sum_{i=1}^{N}\sum_{j=1}^{M}\left[\gcd(i,j)=k\right]\\&= \sum_{i=1}^{\left\lfloor\frac{N}{k}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{M}{k}\right\rfloor}\left[\gcd(i,j)=1\right]\\&= \sum_{d=1}^{\left\lfloor\frac{N}{k}\right\rfloor}\mu(d)\left\lfloor\frac{N}{kd}\right\rfloor\left\lfloor\frac{M}{kd}\right\rfloor\end{aligned}$

$\begin{aligned} &= \prod_{k=1}^{N}{F_{k}}^{\left(\sum_{d=1}^{\left\lfloor\frac{N}{k}\right\rfloor}\mu(d)\left\lfloor\frac{N}{kd}\right\rfloor\left\lfloor\frac{M}{kd}\right\rfloor\right)}\\ &= \prod_{T=1}^{N}\left(\prod_{k|T}{F_{k}}^{\mu(\frac{T}{k})}\right)^{\left\lfloor\frac{N}{T}\right\rfloor\left\lfloor\frac{M}{T}\right\rfloor} \end{aligned}$

令 $f(n)=\prod_{d|n}{F_{d}}^{\mu(\frac{n}{d})}$，可以预处理。

$=\prod_{T=1}^{N}{f(T)}^{\left\lfloor\frac{N}{T}\right\rfloor\left\lfloor\frac{M}{T}\right\rfloor}$

分块。

注意：指数不要取模！

P3911 最小公倍数之和

P3911 最小公倍数之和。

令 $c_i$ 表示 $i$ 出现的次数。

$\sum_{i=1}^n \sum_{j=1}^nc_i \times c_j \times lcm(i,j)$

$\sum_{i=1}^n \sum_{j=1}^nc_i \times c_j \times \frac{i \times j}{gcd(i,j)}$

$\sum_{k=1}^n\sum_{i=1}^n \sum_{j=1}^n [gcd(i,j)=k] c_i \times c_j \times \frac{i \times j}{k}$

$\sum_{k=1}^n\sum_{i=1}^{\lfloor \frac{n}{k} \rfloor } \sum_{j=1}^{\lfloor \frac{n}{k} \rfloor} [gcd(i,j)=1] c_{ik} \times c_{jk} \times i \times j \times k$

$\sum_{k=1}^n\sum_{i=1}^{\lfloor \frac{n}{k} \rfloor } \sum_{j=1}^{\lfloor \frac{n}{k} \rfloor} \sum_{d|gcd(i,j)}\mu(d) \times c_{ik} \times c_{jk} \times i \times j \times k$

$\sum_{k=1}^n\sum_{d=1}^{\lfloor \frac{n}{k} \rfloor} \mu(d) \times d^2 \sum_{i=1}^{\lfloor \frac{n}{kd} \rfloor } \sum_{j=1}^{\lfloor \frac{n}{kd} \rfloor} c_{ikd} \times c_{jkd} \times i \times j \times k$

$\sum_{k=1}^n\sum_{kd=1}^{n}\mu(d) \times d^2\sum_{i=1}^{\lfloor \frac{n}{kd} \rfloor } \sum_{j=1}^{\lfloor \frac{n}{kd} \rfloor} c_{ikd} \times c_{jkd} \times i \times j \times k$

$\sum_{T=1}^n T(\sum_{d|T}\mu(d) \times d )\sum_{i=1}^{\lfloor \frac{n}{T} \rfloor } \sum_{j=1}^{\lfloor \frac{n}{T} \rfloor} c_{iT} \times c_{jT} \times i \times j$

$\sum_{T=1}^n T(\sum_{d|T}\mu(d) \times d ) (\sum_{i=1}^{\lfloor \frac{n}{T} \rfloor } c_{iT} \times i)^2$

左边的括号预处理，右边的暴力。

P5221 Product

P5221 Product。

$\prod_{i=1}^{n}\prod_{j=1}^{n}\frac{lcm(i,j)}{gcd(i,j)}$

$=\prod_{i=1}^{n}\prod_{j=1}^{n}\frac{i*j}{gcd(i,j)^2}$

$=(\prod_{i=1}^{n}\prod_{j=1}^{n}i*j)*(\prod_{i=1}^{n}\prod_{j=1}^{n}gcd(i,j))^{-2}$

左边的直接计算，右边的：

(n!)^{2n}(\Pi_{d=1}^{n}d^{(2\sum_{i=1}^{\frac{n}{d}}\phi(i))-1})^{-2}

\begin{aligned}

\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m} \varphi(ij)

&= \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m} \frac{\varphi(i)\varphi(j)\gcd(i,j)}{\varphi(\gcd(i,j))}

\&= \sum\limits_{d=1}^{n}\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m} \frac{\varphi(i)\varphi(j)d[\gcd(i,j)=d]}{\varphi(d)}

\&= \sum\limits_{d=1}^{n}\frac{d}{\varphi(d)}\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m }\varphi(i)\varphi(j)[\gcd(i,j)=d]

\&= \sum\limits_{d=1}^{n}\frac{d}{\varphi(d)}\sum_{t=1}^{\lfloor\frac{n}{d}\rfloor}\mu(t)\cdot \sum\limits_{i=1}^{\lfloor\frac{n}{dt}\rfloor }\sum\limits_{j=1}^{\lfloor\frac{m}{dt}\rfloor }\varphi(idt)\varphi(jdt)

\&= \sum\limits_{d=1}^{n}\frac{d}{\varphi(d)}\sum_{t=1}^{\lfloor\frac{n}{d}\rfloor}\mu(t)\cdot \sum\limits_{i=1}^{\lfloor\frac{n}{dt}\rfloor }\sum\limits_{j=1}^{\lfloor\frac{m}{dt}\rfloor }\varphi(idt)\varphi(jdt)

\&= \sum\limits_{T=1}^{n}\sum\limits_{d|T} \frac{d\cdot\mu(\frac{T}{d})}{\varphi(d)} \sum\limits_{i=1}^{\lfloor\frac{n}{T}\rfloor }\varphi(ik)\sum\limits_{j=1}^{\lfloor\frac{m}{T}\rfloor }\varphi(jk)

\end{aligned}

\begin{aligned} f(T) = \sum\limits_{d|T} \frac{d\cdot\mu(\frac{T}{d})}{\varphi(d)}\ g(T, n) = \sum\limits_{i=1}^{n}\varphi(iT) \end{aligned}

\sum\limits_{T=1}^{n}f(T)\cdot g(T, \lfloor\frac{n}{T}\rfloor )\cdot g(T,\lfloor\frac{m}{T}\rfloor)

\begin{aligned} t(a,b,n) = \sum\limits_{T=1}^{n}f(T)\cdot g(T,a)\cdot g(T,b) \end{aligned}