首页 > 其他 > 详细

莫比乌斯反演

时间:2018-08-16 13:15:55      阅读:102      评论:0      收藏:0      [点我收藏+]

莫比乌斯反演

 

整除分块 模板

1 for(int l=1,r;l<=n;l=r+1)
2 {
3     r=n/(n/l);
4     ans+=(r-l+1)*(n/l);
5 }

 

莫比乌斯函数:

莫比乌斯函数其实只是一个由容斥系数所构成的函数。

线性筛 模板

 1 void get_mu(int n)
 2 {
 3     mu[1]=1;
 4     for(int i=2;i<=n;i++)
 5     {
 6         if(!vis[i]){prim[++cnt]=i;mu[i]=-1;}
 7         for(int j=1;j<=cnt&&prim[j]*i<=n;j++)
 8         {
 9             vis[prim[j]*i]=1;
10             if(i%prim[j]==0)break;
11             else mu[i*prim[j]]=-mu[i];
12         }
13     }
14  }

 

莫比乌斯反演:

例题:bzoj1101 [POI2007]Zap

 

莫比乌斯反演

原文:https://www.cnblogs.com/weixq351/p/9486372.html

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