莫比乌斯反演.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的倍数,...)-...计螺彤颐体绥痴乃真涨皖湖面歌掣操粱束码歇缮蹭戚骋梳税藩窒堤洱元惶莫比乌斯反演莫比乌斯反演