莫比乌斯反演 - OI Wiki

[Ir1d]

https://oi-wiki.org/math/mobius/#_5

[niltok]

感觉讲得很好啊 读完有种醍醐灌顶的感觉 之前对反演可能有啥误解……

[ghost]

感谢支持！

[PhoenixGS]

请问引理１的证明里是怎么把$\frac{r}{c}$拿掉的？

[Siyuanwww]

@PhoenixGS 请问引理１的证明里是怎么把$\frac{r}{c}$拿掉的？

前面有 0 <= r < 1 的条件

[tiger0132]

兹磁 SiyuanAK

[sshwy]

DSY AK IOI

[pan64271]

Dirichlet卷积的第三个例子应该是 $id * 1$ 吧

[xgzc]

Crash的数字表格那里好像有点小问题，我记得数论分块套数论分块复杂度是$n^{3/4}$的啊

[axiomofchoice-hjt]

莫比乌斯函数 - 补充结论 里面的双箭头是不是应该改成等号？（当时我理解了很久）

[Enter-tainer]

@houjintao 莫比乌斯函数 - 补充结论 里面的双箭头是不是应该改成等号？（当时我理解了很久）

可以说的详细一点吗？

我觉得这里用等价好像挺正常的...？

[mikeyuzihao]

orz siyuaaaan!

[NashChennc]

dirichlet卷积例子第三个应为$\sigma=id*1$,而不是$\sigma=d*1$

[Enter-tainer]

dirichlet卷积例子第三个应为$\sigma=id1$,而不是$\sigma=d1$

求一个 pr

[WineChord]

莫比乌斯函数性质那里的证明有问题，证明部分倒数第二行 $-1$ 的指数应该是 $i$，而且我觉得这个地方应该叫做莫比乌斯函数的定义而非性质。他的性质应该是 $\mu * 1 = \epsilon$，证明的重点应该放在这个性质上，具体可参见 https://en.wikipedia.org/wiki/M%C3%B6bius_function 的 Properties and applications 一节。

[Ir1d]

@WineChord hi 方便开个 pr 帮忙修一下吗

[WineChord]

@Ir1d @WineChord hi 方便开个 pr 帮忙修一下吗

OK 呀，我研究一下怎么开..

[Ir1d]

@WineChord 直接 edit 那个文件然后一路下一步就行（参见 https://oi-wiki.org/intro/faq/#github

[tml104]

用线性筛求莫比乌斯函数那个地方的复杂度是不是不是O(n)的？HAOI2011那题用埃筛和这里的线性筛时间似乎差不多的样子（不过也有可能是因为这题莫比乌斯函数是预处理的所以我没看出来？

[myeeye]

数论分块例题

[H-J-Granger]

前面积性函数的性质和狄卷的例子需不需要证明的啊

[moyujiang]

i了i了

[H-J-Granger]

数论分块的证明显然有误。 希望 id 和 ID 能仅保留一个。 积性函数定义有误。

[Enter-tainer]

@H-J-Granger 积性函数的正确定义应该是怎么样的呢

[H-J-Granger]

@Enter-tainer @H-J-Granger 积性函数的正确定义应该是怎么样的呢

“若……且……”改成“若……则……”？

[mensriwq]

貌似莫比乌斯函数里面那个w(n)是加性函数而不是积性函数

[gsjz]

@SiyuanQAQ

@PhoenixGS 请问引理１的证明里是怎么把$\frac{r}{c}$拿掉的？

前面有 0 <= r < 1 的条件

我还是觉得不能直接拿掉，因为并不保证 $\frac{\lfloor\frac{a}{b}\rfloor}{c}$ 是一个整数。

[Cascol-Chen]

spoj5971那题的代码在spoj上用C++14提交会WA

[Cascol-Chen]

@Cascol-SCUT spoj5971那题的代码在spoj上用C++14提交会WA

发现问题了 质数的时候应该是g[i]=1lli(i-1)+1 爆int了

[sosupro]

话说，莫比乌斯反演第二个式子的证明最后怎么感觉应该是d/n啊qwq

[hehelego]

@sosupro 我也读了一下那个式子. 大概的确是写错了,您来修一下罢

我不是OI wiki的人,这样说话是不是比较奇怪.

[PeterlitsZo]

@gsjz

@SiyuanQAQ

@PhoenixGS 请问引理１的证明里是怎么把$\frac{r}{c}$拿掉的？

前面有 0 <= r < 1 的条件

我还是觉得不能直接拿掉，因为并不保证 $\frac{\lfloor\frac{a}{b}\rfloor}{c}$ 是一个整数。

+1。

[PeterlitsZo]

（引理一）我认为一点点补充是很有必要的：对于 floor(a / b) / c 而言，我们可以断言将它分为整数 floor(floor(a / b) / c) 和分数部分 r'，那么分数部分 r' 一定小于等于 (c - 1) / c。而 r / c 小于 1 / c，加起来就小于 1，那么就可以舍去。

BTW，我觉得这样子不是很优美嗷。如果你们觉得将就的话，那么我可以提交一个 PR。

[RogerGao9673]

建议把数论分块例题换成这个，似乎更简单一点

[mashiroyuki02]

原来前面部分的去哪里了？

[lchen1019]

4.3的证明很多地方用混了符号，下面是我推到的。 $$ \begin{aligned} & \sum{i=1}^n\sum{j=1}^mlcm(i,j)\ = & \sum{i=1}^n\sum{j=1}^m\frac{ij}{gcd{(i,j)}} \ = & \sum{i=1}^n\sum{j=1}^m\sum_{gcd(\frac{i}d,\frac{j}d)=1}\frac{ij}d\ = & \sum{d=1}^{min(n,m)} d \sum{i=1}^n\sum{j=1}^m{\frac{i}d\frac{j}d[gcd(\frac{i}d,\frac{j}d)=1]}\ = & \sum{d=1}^{min(n,m)} d \sum{i'=1}^{\lfloor{\frac{n}d\rfloor}}\sum{j'=1}^{\lfloor{\frac{n}d\rfloor}}{i'j'\sum{r|gcd(i',j')}\mu(r)}\ = & \sum{d=1}^{min(n,m)} d \sum{r=1}^{min(\lfloor{\frac{n}d\rfloor},\lfloor{\frac{m}d\rfloor})}\mu(r)\sum{i=1}^{ \lfloor{\frac{n}d\rfloor}}\sum{j=1}^{ \lfloor{\frac{m}d\rfloor}}ij[r|{i},r|{j}] \ = & \sum{d=1}^{min(n,m)} d \sum{r=1}^{min(\lfloor{\frac{n}d\rfloor},\lfloor{\frac{m}d\rfloor})}\mu(r)r^2\sum{i=1}^{ \lfloor{\frac{n}{dr}\rfloor}}\sum_{j=1}^{ \lfloor{\frac{m}{dr}\rfloor}}i*j \ \end{aligned} $$

我们可以很容易的得到下面的性质，与当前累加符无关的项可以提前： $$ \sum{i=1}^n\sum{j=1}^{m}f(i)g(j)=\sum{i=1}^nf(i)\sum{j=1}^{m}g(j) $$ 于是我们得到最简单的结果： $$ & \sum{d=1}^{min(n,m)} d \sum{r=1}^{min(\lfloor{\frac{n}d\rfloor},\lfloor{\frac{m}d\rfloor})}\mu(r)r^2\frac{(1+\lfloor{\frac{n}{dr}\rfloor})\lfloor{\frac{n}{dr}\rfloor}}2 \frac{(1+\lfloor{\frac{m}{dr}\rfloor})\lfloor{\frac{m}{dr}\rfloor}}2\ $$ 上面的式子使用两次整出分块即可导出结果。