@xzyxzy
2018-08-21T07:44:57.000000Z
字数 5952
阅读 3154
数学
YYB:http://www.cnblogs.com/cjyyb/p/7953803.html
YL:http://www.cnblogs.com/cjoieryl/p/8250019.html
ZSY:http://www.cnblogs.com/zhoushuyu/p/8186224.html
《组合数学》P142写了详细内容,这里简单提一下:
对于任意正整数n,恒有
为的时候很好证明,的如下
首先转化为,,。
那么对于有那么无贡献,推出
在个质数中选个(偶数个系数是,由定义得),选个(奇数个系数是),最后的式子就是(组合数公式)
求:
令
由上面的莫比乌斯函数的定理可以知道
[POI2007]ZAP-Queries(题解戳我)
求下式(预处理,还有拓展到个的Visible Lattice Points)
数字表格(题解戳我)
预处理并且单次询问,其中表示斐波那契数列第i项,
只会用到所以筛的时候可以不用筛到(助力冲榜)
数论分块套路(当数论分块会比较麻烦的时候可以用)
用和表示,然后尝试用和把表示回去,就得到了
,,
,,
,,
数据范围大的时候注意随时取模!!
有时候卡空间/时间,那么能用尽量,随时
《线性筛》
《<约数个数和>题解》
《<安师大sanrd>题解》
筛
void Mobius()
{
mu[1]=1;ispri[1]=1;
for(int i=2;i<=n;i++)
{
if(!ispri[i]) {pri[++tot]=i;mu[i]=-1;}
for(int j=1;j<=tot&&i*pri[j]<=n;j++)
{
ispri[i*pri[j]]=1;
if(i%pri[j])mu[i*pri[j]]=-mu[i];
else break;
}
}
for(int i=1;i<=n;i++)s[i]=s[i-1]+mu[i];
}