首页 > 其他 > 详细

线性筛+求莫比乌斯函数‘

时间:2017-07-26 21:10:51      阅读:490      评论:0      收藏:0      [点我收藏+]

 

莫比乌斯函数、

莫比乌斯函数是一个数论函数,它同时也是一个积性函数(i.e.μ(ab) =μ(a)μ(b), a,b互质)
当n不等于1时,n所有因子的莫比乌斯函数值的和为0,
技术分享
莫比乌斯函数完整定义的通俗表达:
1)莫比乌斯函数μ(n)的定义域是N
2)μ(1)=1
3)当n存在平方因子时,μ(n)=0
4)当n是素数或奇数个不同素数之积时,μ(n)=-1
5)当n是偶数个不同素数之积时,μ(n)=1
技术分享
code
void get()
{
    int n = 100;
    mu[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!ol[i])prime[++num]=i,cout<<i<<" ",mu[i]=-1;
        for(int j=1;j<=num&&j*prime[i]<=n;j++)
        {
            ol[i*prime[j]]=1;
            if((i%prime[j])==0)
            {
                mu[i*prime[j]]=0;
                break;
            }
            mu[i*prime[j]]=-mu[i];
        }
    }
    cout<<num<<endl;
}

 

线性筛+求莫比乌斯函数‘

原文:http://www.cnblogs.com/sssy/p/7241808.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!