Möbius反演

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

ICPCCAMP2015 上关于莫比乌斯反演的内容(十分炫酷): http://vfleaking.blog.uoj.ac/slide/87#/1 


F(n)=∑d|n  f(d)
f(n)=∑d|nμ(d)F(n/d)


sum d|n μ(d) =[n=1]=e(n)
∑d|n μ(d)/d=ϕ(n)/n

1到n中与n互质的数和为n*ϕ(n)/2

ICPCCAMP2015 上关于莫比乌斯反演的内容(十分炫酷): http://vfleaking.blog.uoj.ac/slide/87#/1

F(n)=∑d|n f(d)

f(n)=∑d|nμ(d)F(n/d)

sum d|n μ(d) =[n=1]=e(n)

∑d|n μ(d)/d=ϕ(n)/n

1到n中与n互质的数和为n*ϕ(n)/2