关于莫比乌斯函数的理解
我对莫比乌斯函数有一点点想法,我觉得就是容斥原理衍生出来的.先看一段代码:
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的小屋 文章被收录于专栏
我想要一份甜甜的爱情
我对莫比乌斯函数有一点点想法,我觉得就是容斥原理衍生出来的.先看一段代码:
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的莫比乌斯函数是自己-它所有因子的莫比乌斯函数的值.
其实最优的写法肯定不是这个,而是用欧拉筛来写.
我想要一份甜甜的爱情
相关推荐