? ? ? ? ? ? ? ? ?Mobius　函數除草。。。

? ? ? ? ? ? ? ?

? ? ? ? （1）F(n) = sigma (G(d))?? d | n

? ? ? ? ? ? ? ? ?G(n) = sigma (F(d) * miu (n / d))? d | n

? ? ? ? ? 還有另外一個表達形式?

? ? ? ? （2）F(n) = sigma (G(d))? n | d

? ? ? ? ? ? ? ? ?G(n) = sigma (F(d) * miu (d / n))? n | d

? ? ? ? ? 形式（1）的證明利用了逆元的思想，

? ? ? ? ? 形式（2）本質上等價于容斥定理（自己想想容斥定理的原理就知道了）

? ? ? ? ? 令滿足1 <= a <= N, 1 <= b <= N, gcd(a, b) = k的個數為G(k), gcd(a,b)

? ? ? ? ? 為k的倍數的個數為F(k)

? ? ? ? ? 則有F(n) = sigma(G(d)) n|d

? ? ? ? ? 所以有G(n) ?= sigma(F(d)*miu(d/n)) n| d

? ? ? ? ? 到這里本題基本上就解決了，至于Mobius函數的求法可以參見JZB的線性篩。。。

??

總結

以上是生活随笔為你收集整理的SRM 613 div1 500pt的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。