(以下除号皆表示整除)
对于一些式子复杂度大的数论题,或许用莫比乌斯反演可以高效解决问题。

前置技能:
– 基本数论函数
– 狄利克雷卷积

莫比乌斯函数满足 $\mu \cdot I = \epsilon $
即 $ \sum_{d|n}\mu(d) = [n = 1] $
表达式为:
$$ n = 0 : \mu(n) = 1 $$
$$ n = \prod_{p|n\&p\,is\,prime} p : \mu(n)=(-1)^k $$
$$ otherwise : \mu(n)=0 $$

证明:
暂时不会

莫比乌斯反演:
对于数论函数 f(n),设 $ F(n) = \sum_{d|n}f(d) $
即 $ F = f \cdot I $
则有 $ f(n) = \sum_{d|n}F(d) \cdot \mu(\frac{n}{d}) $
即 $ f = F \cdot \mu $

证明:

$$ \because \; F = f \cdot I $$
$$ \therefore \; F \cdot \mu = f \cdot I \cdot \mu $$
$$ \because \; I \cdot \mu = \epsilon $$
$$ \therefore \; F \cdot \mu = f \cdot \epsilon $$
$$ \therefore \; f = F \cdot \mu $$

莫比乌斯反演好像主要是用来推式子,F 比 f 好做的话,就可以试试莫比乌斯反演。


1 条评论

small business blogging · 2019年8月23日 下午1:46

Very good information. Lucky me I recently found your blog by chance (stumbleupon). I’ve bookmarked it for later!

发表评论

电子邮件地址不会被公开。 必填项已用*标注