网站建设与管理认识,北京建筑设计院加盟,重庆市工程建设信息网新网站,自己有网站做点什么索引 莫比乌斯反演1 定理莫比乌斯反演2 证明莫比乌斯反演3 技巧前言 本篇内容全部为定理#xff0c;无证明 定义 莫比乌斯函数的符号为\(\mu\)#xff0c;通俗的来讲\[ \mu(n) \left\{ \begin{matrix} 1 n1\\ (-1)^k n p_1p_2p_3\dots p_k\\ 0 \text{其他…索引 莫比乌斯反演1 定理莫比乌斯反演2 证明莫比乌斯反演3 技巧前言 本篇内容全部为定理无证明 定义 莫比乌斯函数的符号为\(\mu\)通俗的来讲\[ \mu(n) \left\{ \begin{matrix} 1 n1\\ (-1)^k n p_1p_2p_3\dots p_k\\ 0 \text{其他情况} \end{matrix} \right. \] 简单的说就是如果\(n 1\), \(\mu(n) 1\)\(n\)的因数多于两个时\(\mu(d)(-1)^k\)\(k\)为\(n\)的因数个数其余时候\(\mu(n)0\)。 其实真正的定义式如下\[\sum_{d|n} \mu(d)[n1]\] 然而方便起见我们还是采用最上面那个。 莫比乌斯函数的三个性质 1、莫比乌斯函数在n1时\(\sum_{d|n}\mu(d)\)为1其他时候为0\[\sum_{d|n} \mu(d)[n1]\] P.S.这条本来不是性质是定义 2、莫比乌斯函数是积性函数不完全积性 即:\[\mu(m \times n) \mu(m) \times \mu(n)\]\[\text{当且仅当}gcd(m,n)1\] 3、对于任意的整数n\[\sum_{d|n}\frac{\mu(d)}{d}\frac{\phi(n)}{n}\] 莫比乌斯反演 形式A 若在\(N^\)上有两个函数\(f(n)\)和\(g(n)\)满足\[g(n)\sum_{d|n}f(n)\] 那么\[f(n)\sum_{d|n}\mu(d)g(\frac{n}{d})\] 形式B 若在\(N^\)上有两个函数\(f(n)\)和\(g(n)\)满足\[g(n)\sum_{d|n}f(n)\] 那么\[f(n)\sum_{n|d}\mu(\frac{d}{n})g(d)\] 计算莫比乌斯函数 做法A:定义法 暴力枚举每一个数的质因子及其幂次根据定义判断即可。效率较低。 做法B:线性筛 前文讲到了莫比乌斯函数是积性函数那么我们珂以用线性筛来计算 首先可以确定的是质数的函数值一定是\(-1\) 然后如果是被素数更新到的合数那么每一次都取反1变-1-1变1。要保证被最小的质因子更新 代码 void getMu(int n){mu[1] 1; is_not_prime[0] is_not_prime[1] 1;for (int i 2; i n; i){if (!is_not_prime[i]) mu[primes[prime_num] i] -1;for (int j 1; j prime_num primes[j] * i n; j){is_not_prime[i * primes[j]] 1;if (!(i % primes[j])) break;elsemu[primes[j] * i] -mu[i];}}
} 参考资料 莫比乌斯反演 作者[中]·Gaussian 参考内容:部分性质「莫比乌斯反演」学习笔记 作者[中]·Chhokmah 参考内容:莫比乌斯函数的计算 转载于:https://www.cnblogs.com/linzhengmin/p/10994520.html
