当前位置 博文首页 > wennitao的博客：莫比乌斯反演、杜教筛
莫比乌斯反演基本形式：
对于一个函数 f ( x ) f(x) f(x)
设 g ( x ) = ∑ x ∣ d f ( d ) g(x)=\sum _{x \mid d} f(d) g(x)=∑x∣d?f(d)，那么
f ( x ) = ∑ x ∣ d μ ( d x ) ? g ( d ) f(x)=\sum _{x \mid d} \mu(\frac {d} {x}) \cdot g(d) f(x)=∑x∣d?μ(xd?)?g(d)
1 1 1： f ( x ) = 1 f(x)=1 f(x)=1
e e e： f ( x ) = [ x = 1 ] f(x) = [x = 1] f(x)=[x=1]
i d id id： f ( x ) = x f(x) = x f(x)=x
推式子：
1到 n n n与 n n n互质的数的个数： ∑ i = 1 n [ g c d ( i , n ) = 1 ] \sum _{i=1} ^{n} [gcd (i, n) = 1] ∑i=1n?[gcd(i,n)=1]
令 f ( x ) = ∑ i = 1 n [ g c d ( i , n ) = x ] f(x)=\sum _{i=1} ^{n} [gcd (i, n) = x] f(x)=∑i=1n?[gcd(i,n)=x]
g ( x ) = ∑ x ∣ d f ( d ) = ∑ x ∣ d ∑ i = 1 n [ g c d ( i , n ) = d ] = ∑ i = 1 n [ x ∣ g c d ( i , n ) ] = { ? n x ? , x ∣ n 0 , x ? ∣ n g(x) = \sum _{x \mid d} f(d) = \sum_{x \mid d} \sum _{i=1} ^{n} [gcd (i, n) = d] = \sum _{i=1} ^{n} [x \mid gcd (i, n)] \\ = \begin {cases} \lfloor \frac {n} {x} \rfloor, & x \mid n \\ 0, & x \not\mid n \end {cases} g(x)=∑x∣d?f(d)=∑x∣d?∑i=1n?[gcd(i,n)=d]=∑i=1n?[x∣gcd(i,n)]={?xn??,0,?x∣nx??
