铺垫
已知(g(n))的前缀和(f(n)=sum_{I=1}^ng(i)),则可以通过f来反求g,(g(n)=f(n)-f(n-1))
已知(g(n))的因数和(f(n)=sum_{d|n}g(d)),如何通过f来反求g
(g(n)=g(p_1^{alpha1}p_2^{alpha2}p_3^{alpha3}···p_k^{alpha k})=sum_{Ssubseteq{1,2,···,k}}(-1)^{|s|}f(p_1^{alpha1-i_1}p_2^{alpha2-i_2}···p_k^{alpha k-i_k}))
((jin S quad i_j=1 否则i_j=0))
定理(莫比乌斯反演1)
设(f:N
ightarrow R :::::g:N
ightarrow R)是两个函数
则
(f(n)=sum_{d|n}g(d))
(g(n)=sum_{d|n}mu(frac{n}{d})f(d)) (quadquadmu(n)=
egin{cases}
(-1)^k& ext{if n没有幂次大于平方的质因子，且有k个质因子}\
0& ext{if n有大于平方因子}
end{cases})
定理(莫比乌斯反演2)
设(f:N
ightarrow R :::::g:N
ightarrow R)是两个函数，且存在正整数N,对于所有(n>N,f(n)=g(n)=0)
则
(f(n)=sum_{n|m, mleq N}g(m))
(g(n)=sum_{n|m,mleq N}mu(frac{m}{n})f(m))