对\(d\)进行质因数分解：\(d=p_1^{r1}p_2^{r2}p_3^{r3}····p_k^{rk}\)\(r=max\{r_1,r_2,r_3···r_k\}\) 莫比乌斯函数的定义为\[\mu(d) = \begin{cases}1\qquad d=1\\ 0\qquad r > 1\\ (-1)^k\qquad r=1\end{cases}\] 也就是说
当\(d=1\)时，\(\mu(d)=1\)当\(d\)质因数分解后，若质因子中的最大次数大于一，\(\mu(d)=0\)当\(d\)质因数分解后，质因子中的最大次数等于一，也就是\(d=p_1p_2p_3···p_k\)时，\(\mu(d)=(-1)^k\)，\(k\)为质因子的个数举个栗子：\(\mu(1)=1\\ \mu(3)=(-1)^1=-1\\ \mu(6)=(-1)^2=1\\\mu(4)=0\)
性质1： 对于任意正整数\(n\)，有\[\sum_{d\mid n}\mu(d)=[n=1]\]\([n=1]\)表示当\(n=1\)的时候值为\(1\)，否则值为\(0\)。
证明(请教于wby大佬): 当\(n=1\)时，显然。 考虑\(n>1\)的情况，\(n=p_1^{k1}o_2^{k2}p_3^{k3}···p_m^{km}\) 根据定义显然只有当\(k_1=k_2=k_3=···k_m=1\)时有贡献，否则为\(0\)。 我们就只讨论有贡献的情况； 设\(n\)的因子\(d\)中有\(i\)个质因子，\(\mu(d)=(-1)^r\)，因为\(d\)的质因子一定是\(n\)的质因子，从\(m\)个质因子中选出\(i\)的质因子的组合数就为\(C_m^r\)。\[\sum_{d\mid n}\mu(d)=\sum_{r=0}^{m}(-1)^{i} C_m^r\] 然后根据二项式定理：\[(x+y)^m = \sum_{r=0}^{m}C_{m}^{r} x^{m-r} y^r\] 令\(x=1,y=-1\)，可得：\[\sum_{r=0}^{m}C_m^r(-1)^{r}=\sum_{r=0}^{m}C_m^r (1)^{m-r}(-1)^r=(-1+1)^m=0\] 由此得证 ****
性质2： 对于任意正整数\(n\)均有\[\sum_{d\mid n} \frac{\mu(d)}{d}=\frac{\phi(n)}{n}\]
证明：\[\phi(n)=\sum_{i=1}^{n}[gcd(i,n)==1]\] 这时根据性质1\[\phi(n)=\sum_{i=1}^{n}\sum_{d\mid gcd(i,j)}\mu(d)\] 然后先枚举最大公约数\[ \begin{aligned} \phi(n)=&\sum_{d\mid n}\sum_{d\mid i=d}^{i\leq n}\mu(d)\\ =&\sum_{d\mid n}\mu(d)\sum_{d\mid i=d}^{i\leq n}1\\ =&\sum_{d\mid n}\mu(d)\frac{n}{d}\\ =&\sum_{d\mid n}\frac{\mu(d)n}{d}\end{aligned} \] 得到\[\frac{\phi(n)}{n}=\sum_{d\mid n} \frac{\mu(d)}{d}\] ****
只需要在筛法上加四句话
void shai(int n) { mu[1] = 1; //定义mu[1]=1 for(int i = 2; i <= n; i++) { if (!vis[i]) p[++num] = i, mu[i] = -1; //mu质数=-1 for (int j = 1; j <= num; j++) { if (i * p[j] > n) break; vis[i * p[j]] = 1; if (!i % p[j]) { //i%p[j]==0说明i有p[j]这个因子，所以i*p[j]=0 mu[i * p[j]] = 0; break; } else mu[i * p[j]] = -mu[i]; //有多了一个质因子，所以取负 } } }略微说明了一下莫比乌斯函数函数后，就迎来最重要的内容，莫比乌斯反演。 定义： 如果F(n)，f(n)是数论函数，且满足\[F(n)=\sum_{d\mid n}f(d)\] 则有反演：\[f(n)=\sum_{d\mid n}\mu(d)F(\frac{n}{d})\]
证明： 将\(F(\dfrac{n}{d})\)带入得\[\sum_{d\mid n}\mu(d)F(\frac{n}{d})=\sum_{d\mid n}(\mu(d)\sum_{k\mid \frac{n}{d}}f(k))\] 观察后面的式子，发现要满足\(\dfrac{n}{d}\div k=0\)，所以实际上就是要求\[k\times d=n\] 那我们就可以理解为对于所有的二元组\((\mu(d),f(k))\)都能被枚举到 所以我们枚举\(k\)， 式子就变成了\[\sum_{k\mid n}(f(k)\sum_{k*d\mid n}\mu(d))\] 再转换一下，变成\[\sum_{k\mid n}(f(k)\sum_{d\mid \frac{n}{k}}\mu(d))\] 然后根据莫比乌斯函数的性质1 只有当\(k=n\)时，\(\sum_{d\mid \frac{n}{k}}\mu(d)=1\)，其余情况为\(0\)； 于是原式=\(f(n)\) ****
莫比乌斯反演的另一种形式： 当\[F(n)=\sum_{n\mid d}f(d)\]时\[f(n)=\sum_{n\mid d}f(d)\mu(\frac{d}{n})\]
转载于:https://www.cnblogs.com/lykkk/p/10663073.html
相关资源：JAVA上百实例源码以及开源项目