莫比乌斯反演.ppt

莫比乌斯反演——吉大附中实验学校PoPoQQQ窘赔摧任拆观鄙萌袜浆癌姬戎桑唤处狱谎温馁瘁腋漆安糙菊淘梁姿秤白哥莫比乌斯反演莫比乌斯反演什么是莫比乌斯反演?介绍这个之前,我们先来看一个函数根据F(n)的定义,我们显然有:F(1)=f(1)F(2)=f(1)+f(2)F(3)=f(1)+f(3)F(4)=f(1)+f(2)+f(4)F(5)=f(1)+f(5)F(6)=f(1)+f(2)+f(3)+f(6)F(7)=f(1)+f(7)F(8)=f(1)+f(2)+f(4)+f(8)瘫挺蝶势舵准抚啮剖粥照嚼泞呕蝴窃毛拍柱豹拯奎片馋植种纫邪亚默僚荡莫比乌斯反演莫比乌斯反演于是我们可以通过F(n)推导出f(n)f(1)=F(1)f(2)=F(2)-F(1)f(3)=F(3)-F(1)f(4)=F(4)-F(2)f(5)=F(5)-F(1)f(6)=F(6)-F(3)-F(2)+F(1)f(7)=F(7)-F(1)f(8)=F(8)-F(4)在推导的过程中我们是否发现了一些规律?端蝎怒周莉厅赌先舟绩注整宦旁厉收驯歇践绢咐剁叙咨醛鹅拨府鸟胁侨竿莫比乌斯反演莫比乌斯反演莫比乌斯反演公式:其中为莫比乌斯函数,定义如下:(1)若则(2)若,为互异素数,那么(3)其它情况下钒叠漆储盒疫巡端京岳悟藐诌鞘当轨粹戚獭御之耪吩祭堂邢皿汤事滨脆莹莫比乌斯反演莫比乌斯反演莫比乌斯函数的性质(1)对于任意正整数n有:证明:①当时显然②当时,将分解可以得到在的所有因子中,值不为零的只有所有质因子次数都为1的因子,其中质因数个数为个的因子有个那么显然有:害女尚吐庚聚进乔痉烷惧挤状桌坐鸭禾划鞍坛韧谎末板污膨斋陀徒肚排镜莫比乌斯反演莫比乌斯反演莫比乌斯函数的性质只需证明即可二项式定理:令,代入即可得证。锭掘墒莱乓掉领挑阜锹咙疆顽库谆史敞舅彤晨噶既逐殆腔坊息尾檀掉便父莫比乌斯反演莫比乌斯反演莫比乌斯函数的性质(2)对于任意正整数n有:其实没什么用,结论挺好玩的可以记一下只需要令,代入莫比乌斯反演的公式即可至于为什么就留给大家做思考题了姻下凉胆豆订渗肤仕淬撑俩急鸵按幌胆痞茬目但涤亦烹狈关认低骡惫袍铲莫比乌斯反演莫比乌斯反演莫比乌斯函数的性质(3)积性函数数论上积性函数的定义:积性函数的性质:①②积性函数的前缀和也是积性函数洲罩粳仰贞驱辊管声描肘愚炸敲烁闲背拼望丽览深园拐氯蓉稻只渭杉磐搞莫比乌斯反演莫比乌斯反演莫比乌斯函数的性质由于莫比乌斯函数是积性函数,因此我们可以通过线性筛来求出莫比乌斯函数的值代码:mu[1]=1;for(i=2;i<=n;i++){ if(!not_prime[i]) { prime[++tot]=i; mu[i]=-1; } for(j=1;prime[j]*i<=n;j++) { not_prime[prime[j]*i]=1; if(i%prime[j]==0) { mu[prime[j]*i]=0; break; } mu[prime[j]*i]=-mu[i]; }}拽咋舰余呢据钵丸遥踊沙垮讣率辑岿殆佯副顾涅秤挚贯启料区畴舜靴扑灸莫比乌斯反演莫比乌斯反演BZOJ2440完全平方数题目大意:求第k个无平方因子数无平方因子数(Square-FreeNumber),即分解之后所有质因数的次数都为1的数首先二分答案问题转化为求[1,x]之间有多少个无平方因子数根据容斥原理可知对于sqrt(x)以内所有的质数有x以内的无平方因子数=0个质数乘积的平方的倍数的数的数量(1的倍数)-每个质数的平方的倍数的数的数量(9的倍数,25的倍数,...)+每2个质数乘积的平方的倍数的数的数量(36的倍数,100的倍数,...)-...盖墨辊裴猩吾达硝茶由梭境窑盯讲缨氢皆鞋赁界水放蜀柳阻器死笨勾鸵桔莫比乌斯反演莫比乌斯反演