关于莫比乌斯函数的理解

我对莫比乌斯函数有一点点想法,我觉得就是容斥原理衍生出来的.先看一段代码:

mu[1]=1;
    for (int i=1;i<=m;i++)
        for (int j=2;j<=m/i;j++)
            mu[i*j]=mu[i*j]-mu[i];

可以发现到了i*j的莫比乌斯函数是自己-它所有因子的莫比乌斯函数的值.
其实最优的写法肯定不是这个,而是用欧拉筛来写.

lpt的小屋 文章被收录于专栏

我想要一份甜甜的爱情

全部评论

相关推荐

去B座二楼砸水泥地:不过也可以理解,这种应该没参加过秋招
点赞 评论 收藏
分享
4 收藏 评论
分享
牛客网
牛客企业服务