Mobius-Transformation

Posted on Edited on In

这个菜鸡现在还什么都不会>_>慢慢更新吧

前置知识

整除分块

设\(f(x) = \lfloor \frac{k}{x} \rfloor\)

\(f(x)\)分布呈块状,对于任意一个\(i\),有最大的\(j = \lfloor \frac{k}{\lfloor \frac{k}{i} \rfloor} \rfloor\),使得\(f(i) == f(i+1) == ... = f(j)\)

对于类似\(\sum_{i = 1}^{n}\lfloor \frac{k}{i} \rfloor\)的式子,可分块在\(O(\sqrt{n})\)时间内计算完毕

代码:

1
2
3
4
5
for(int l = 1;l <= n;l = r+1){
		if(k/l)r = min(n,k/(k/l));
		else r = n;
		ans += (r-l+1)*(k/l);
	}

狄利克雷(Dirichlet)卷积

定义

设\(f,g\)为两个数论函数,其狄利克雷卷积\(f*g\)为: \[ f \ast g(n) = \sum_{d|n}f(d)g(\frac{n}{d}) \]

常用式子

$$ \[\begin{aligned} \varepsilon=\mu \ast 1&\iff\varepsilon(n)=\sum_{d\mid n}\mu(d)\\ d=1 \ast 1&\iff d(n)=\sum_{d\mid n}1\\ \sigma=\text{id} \ast 1&\iff\sigma(n)=\sum_{d\mid n}d\\ \varphi=\mu \ast \text{id}&\iff\varphi(n)=\sum_{d\mid n}d\cdot\mu(\frac{n}{d}) \\ \end{aligned}\]

$$

常用结论

\[ \sum_{d|n}^n\varphi(d) = n \]

\[ [\gcd(i,j) == 1] = \epsilon(\gcd(i,j) = \sum_{d|\gcd(i,j)}\mu(d) \]

套路题

\(\sum_{i=1}^ngcd(i,n)\)

\[ \begin{align} &\sum_{i=1}^n\gcd(i,n)\\ &=\sum_{d|n}d\sum_{i=1}^n[\gcd(i,n)==d]\\ &=\sum_{d|n}d\sum_{i=1}^{\frac{n}{d}}[\gcd(i,n)==1]\\ &=\sum_{d|n}d\cdotφ(\frac{n}{d}) \end{align} \]

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

\[ \begin{align} &\sum_{i = 1}^n\sum_{j=1}^n\gcd(i,j)\\ &= \sum_{d=1}^nd\sum_{i=1}^n\sum_{j=1}^n[gcd(i,j) == d]\\ &=\sum_{d=1}^nd\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{n}{d}}[gcd(i,j)==1]\\ &=\sum_{d=1}^nd(2\cdot\sum_{i=1}^{\frac{n}{d}}\varphi(i) - 1) \end{align} \]

关于最后一步,我们设\(f(x) = \sum_{i=1}^{n}\sum_{j=1}^{n}[gcd(i,j)==1]\)

手画一下,容易看出\(f(x) = 2\cdot\sum_{i=1}^n\varphi(i) - 1\)

另一种做法:

我们知道\(\varphi\)有这么一个性质,\(\sum_{d|n}^{n}\varphi(d) = n\)

也就是\(\sum_{d|\gcd(i,j)}^{n}\varphi(d) = \gcd(i,j)\)

那么: \[ \begin{align} &\sum_{i = 1}^n\sum_{j = 1}^n\gcd(i,j)\\ &=\sum_{i=1}^n\sum_{j=1}^n\sum_{d|\gcd(i,j)}\varphi(d)\\ &=\sum_{d = 1}^n\varphi(d)\sum_{i=1}^n[d|i]\sum_{j=1}^n[d|j]\\ &=\sum_{d = 1}^n\varphi(d)\cdot\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor \end{align} \] 少处理个前缀和=-=而且我感觉这个做法更好理解

例题:洛谷P2398

\(\sum_{i = 1}^{n}\sum_{j=i+1}^{n}\gcd(i,j)\)

和上面那个基本一样 \[ \begin{align} &\sum_{i = 1}^n\sum_{j=i+1}^n\gcd(i,j)\\ &= \sum_{d=1}^nd\sum_{i=1}^n\sum_{j=i+1}^n[gcd(i,j) == d]\\ &=\sum_{d=1}^nd\sum_{i=1}^{\frac{n}{d}}\sum_{j=i+1}^{\frac{n}{d}}[gcd(i,j)==1]\\ &=\sum_{d=1}^nd(\sum_{i=1}^{\frac{n}{d}}\varphi(i) - 1) \end{align} \] (最后一步的化简和上一题大同小异,手画一下就有了)

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

前置知识: \[ \epsilon(n)=\sum_{d|n}\mu(d)= \begin{cases} 1&n=1\\ 0&otherwise \end{cases} \]

开始愉快地推式子: \[ \begin{align} &\sum_{i=1}^{n}\sum_{i=1}^{m}[\gcd(i,j) == 1] \\ &=\sum_{i=1}^{n}\sum_{i=1}^{m}\epsilon(\gcd(i,j))\\ &=\sum_{i=1}^{n}\sum_{i=1}^{m}\sum_{d|gcd(i,j)}\mu(d)\\ &=\sum_{d = 1}^{\min(n,m)}\mu(d)\sum_{i = 1}^n[d|i]\sum_{j = 1}^{m}[d|j]\\ &=\sum_{d=1}^{\min(n,m)}\mu(d)\lfloor \frac{n}{d}\rfloor \lfloor \frac{m}{d} \rfloor \end{align} \] 同理,我们有: \[ \sum_{i = 1}^n\sum_{j = 1}^n\sum_{k = 1}^n [\gcd(i,j,k) == 1] = \sum_{d = 1}^n \mu(d)(\lfloor \frac{n}{d}\rfloor)^3 \]