莫比乌斯变换教育课件.ppt

1、引言莫比乌斯变换1)复平面上的莫比乌斯变换公元1858年,德国数学家莫比乌斯(Mobius,1790~1868)发现:把一个扭转180°后再两头粘接起来的纸条,具有魔术般的性质。这样的纸带只有一个面(即单侧曲面),一只小虫可以爬遍整个曲面而不必跨过它的边缘!这种由莫比乌斯发现的神奇的单面纸带,称为“莫比乌斯带”。几何学中的莫比乌斯变换:其中z,a,b,c,d为复数且满足ad−bc、引言莫比乌斯变换2)数论中的莫比乌斯变换对于给定的数论函数f(n),(nN),定义新的数论函数称F(n)为f(n)的莫比乌斯变换,而f(n)为F(n)的莫比乌斯逆变换。2020/3/292、数论莫比乌斯变换计算实例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)2020/3/29莫比乌斯逆变换计算实例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)2020/3/293、逆变换与莫比乌斯函数观察发现f(n)的表示式中有形式为F(n/d)的项。引入莫比乌斯函数(n),记(d)为F(n/d)的符号+或-之一有(1)=(6)=1,(2)=(3)=(5)=(7)=-1,(4)=(8)=0。若p是素数,由F(p)=f(1)+f(p),得f(p)=F(p)-F(1),因此(p)=-1。继续观察,F(p2)=f(1)+f(p)+f(p2),得f(p2)=F(p2)-(F(p)-F(1))-F(1)=F(p2)-F(p),这又有(p2)=0。同理推出,f(p3)=F(p3)-F(p2),这又有(p3)=0,继续推下去,有当k>1,有(pk)=0。2020/3/29莫比乌斯函数(n)继续观察:设p1,p2为不同素数F(p1*p2)=f(p1*p2)+f(p1)+f(p2)+f(1),得f(p1*p2)=F(p1*p2)-F(p1)-F(p2)+F(1)。这里有(1)=1,(p2)=-1,(p1)=-1,(p1*p2)=1。2020/3/29莫比乌斯函数(n)总结得2020/3/29积性函数积性函数f(n):对数论函数f(n),如果满足对任意正整数m,n,只要gcd(m,n)=1,就有f(mn)=f(m)f(n),那么称f(n)为积性函数完全积性函数g(n):对数论函数g(n),如果满足对任意正整数m,n,均有g(mn)=g(m)g(n),那么称g(n)完全积性函数2020/3/29莫比乌斯函数的性质莫比乌斯函数是积性函数,即若gcd(m,n)=1,则(mn)=(m)(n);若gcd(m,n)>1,则(mn)=0;对于f(n)=1的特例,证明:首先(n)是积性函数,因此用下面将证明的一个命题可知I(n)也是积性函数。显然,I(1)=1;而对素数p,I(pt)=1+(p)+(p2)+…+(pt)=1-1+0+…+0=(){//计算d的不同素因子个数,计算(d)的值memset(vis,0,sizeof(vis));//vis[i]记录记录i是否标记过mu[1]=t=0;for(inti=2;i<N;i++){if(!vis[i]){//如果vis[i]是第1个未标记的,t++]=i;mu[i]=-1;}for(intj=0;t&&i*prime[j]<N;j++){//用筛法求素数vis[i*prime[j]]=1;//将prime[j]的倍数都标记,即筛掉if(i%prime[j])mu[i*prime[j]]=-mu[i];//若i未被筛掉,则用积性求else{mu[i*prime[j]]=0;break;//被筛掉的数都有素数的平方,=0}}}}2020/3/29