莫比乌斯函数
定义:
-
一个正整数\(d\),由算术基本定理可得\(d=p_1^{c_1}*p_2^{c_2},...,p_m^{c_m}\)。
-
当\(d=1\)时,\(\mu(1)=1\)。
-
若\(d\)无平方数因数,且\(d=p_1,...,p_k\),\(\mu(d)=(-1)^k\)。
- 也就是当\(d\)的所有质因子各不相等时,若\(d\)有偶数个质因子时,\(\mu(d)=1\);若有奇数个质因子时,\(\mu(d)=-1\)。
-
若\(d\)有大于\(1\)的平方数因数,\(\mu(d)=0\)。(也就是\(c_i\neq1\))
-
举一下例子吧。
-
\(d=1\),因为\(d=1\),所以\(\mu(d)=1\)。
-
\(d=2\),\(d=2=2\),即有奇数个质因子,\(\mu(d)=-1\)。
-
\(d=4\),\(d=4=2^2\),\(d\)有大于1的平方数因数,\(\mu(d)=0\)。
-
\(d=6\),\(d=2*3\),即有偶数个质因子,\(\mu(d)=1\)。
性质:
-
莫比乌斯函数是一个积性函数。
-
积性函数:\(a,b\)互质,有\(f(ab)=f(a)*f(b)\),称\(f\)为积性函数。
-
证明:分情况讨论一下就行。
求法:
- 如果只用求一项,那么直接质因数分解一下就行。
- 就像求欧拉函数可以用线性筛法求一样,莫比乌斯函数可以用线筛筛法求出。
void get_mu(int n)
{
mu[1] = 1;
for(int i = 2; i <= n; i++)
{
if(!vis[i])
{
primes[++cnt] = i;
mu[i] = -1;
}
for(int j = 1; primes[j] <= n/i; j++)
{
vis[primes[j]*i] = 1;
if(i % primes[j] == 0) break;
else mu[i*primes[j]] = -mu[i];
}
}
}
原文链接: https://www.cnblogs.com/zxytxdy/p/12166374.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/191653
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!