莫比乌斯反演.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) | ( ) ( ) d n F n f d ??于是我们可以通过 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) 其它情况下| | ( ) ( ) ( ) ( ) ( ) d n d n n F n f d f n d F d ?? ??? ?( ) d?1d?( ) 1 d?? 1 2 ... k d p p p ? ip ( ) ( 1) kd?? ?( ) 0 d??莫比乌斯函数的性质?(1) 对于任意正整数 n有: ?证明: ?①当时显然?②当时,将分解可以得到?在的所有因子中, 值不为零的只有所有质因子次数都为1的因子,其中质因数个数为个的因子有个?那么显然有: | 1 ( 1) ( ) 0 ( 1) d nndn ???????? 1n?1n? n 1 2 1 2 ... ka a a k n p p p ? n ? 0 1 2 | 0 ( ) ... ( 1) ( 1) k k k i i k k k k k d n i d C C C C C ??? ???????? ? r rkC莫比乌斯函数的性质?只需证明即可?二项式定理: ?令,代入即可得证。 0 ( 1) 0 ( ) n i i ni C n N ??? ??? 0 ( ) n n i i n i ni x y C x y ??? ?? 1, 1 x y ?? ?莫比乌斯函数的性质?(2) 对于任意正整数 n有: ?其实没什么用,结论挺好玩的可以记一下?只需要令,代入莫比乌斯反演的公式即可?至于为什么就留给大家做思考题了| ( ) ( ) d n d n d n ? ???( ) , ( ) ( ) F n n f n n ?? ?| ( ) d n n d ???莫比乌斯函数的性质?(3) 积性函数?数论上积性函数的定义: ?积性函数的性质: ?①?②积性函数的前缀和也是积性函数( ) ( , ) 1 ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) f n N x y f xy f x f y f n x y f xy f x f y f n ?? ??设为一个定义在集合上的函数,如果对于任意有,则称为一个积性函数;若对于任意和均有, 则称为一个完全积性函数(1) 1 f?莫比乌斯函数的性质?由于莫比乌斯函数是积性函数,因此我们可以通过线性筛来求出莫比乌斯函数的值?代码: ? 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_p