《莫比乌斯变换》由会员分享，可在线阅读，更多相关《莫比乌斯变换（51页珍藏版）》请在金锄头文库上搜索。
1、* 莫比乌斯变换 上海大学 沈云付 yfshen 上海大学计算机工程与科学学院 1、引言 莫比乌斯变换 1）复平面上的莫比乌斯变换 公元1858年，德国数学家莫比乌斯(Mobius，1790 1868)发现：把一个扭转180后再两头粘接起来 的纸条，具有魔术般的性质。这样的纸带只有一个 面(即单侧曲面)，一只小虫可以爬遍整个曲面而不 必跨过它的边缘！这种由莫比乌斯发现的神奇的单 面纸带，称为“莫比乌斯带”。 几何学中的莫比乌斯变换： 其中 z, a, b, c, d 为 复数 且满足 adbc0. * 1、引言 莫比乌斯变换 2）数论中的莫比乌斯变换 对于给定的数论函数f(n)，（nN），定义
2、新的数 论函数 称F(n)为f(n)的莫比乌斯变换，而f(n)为F(n)的莫 比乌斯逆变换。 * 2、数论莫比乌斯变换计算实例 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(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、3)-F(2)+F(1) f(7)=F(7)-F(1) f(8)=F(8)-F(4) * 3、逆变换与莫比乌斯函数 观察发现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。 同理推出，
4、f(p3)=F(p3)-F(p2)，这又有(p3)=0，继续推下去 ，有当k1，有(pk)=0。 * 莫比乌斯函数(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。 * 莫比乌斯函数(n) 总结得 * 积性函数 积性函数f(n) ：对数论函数f(n)，如果满足对任意 正整数m，n，只要gcd(m,n)=1，就有 f(mn)=f(m)f(n)，那么称f(n)为积性函数 完全积性函数g
5、(n) ：对数论函数g(n)，如果满足 对任意正整数m，n，均有g(mn)=g(m)g(n)，那么 称g(n)完全积性函数 * 莫比乌斯函数的性质 莫比乌斯函数是积性函数，即 1. 若gcd(m,n)=1，则(mn)= (m) (n)； 2. 若gcd(m,n)1，则(mn)=0； 3. 对于f(n)=1的特例， 证明：首先(n)是积性函数，因此用下面将证明的一 个命题可 知I(n)也是积性函数。显然，I(1)=1; 而对素数p，I(pt)=1+ (p)+ (p2)+(pt) =1-1+0+0=0. 证毕 * 计算莫比乌斯函数的程序实现 void Mobius() /计算d的不同素因子个数，计
6、算(d)的值 memset(vis,0,sizeof(vis); /visi记录记录i是否标记过 mu1 = 1; cnt = 0; for(int i=2; iN; i+) if(!visi) /如果visi是第1个未标记的，那么i是素数 primecnt+ = i; mui = -1; for(int j=0; jcnt j+) /用筛法求素数 visi*primej = 1; /将primej的倍数都标记，即筛掉 if(i%primej) mui*primej = -mui; /若i未被筛掉，则用积性求 else mui*primej = 0; break; /被筛掉的数都有素数的平方，
7、 =0 * 4、莫比乌斯函数性质-定理1 定理1：设f(n)和 F(n)均为定义在N上的数论函数， f(n)不 恒为0，若f(n)为积性函数，则F(n)也为积性函数。 证：设n有标准分解 已知 F(1)=f(1)=1。n的任一正因子d，可写为 因此 * 因此，F(n)为积性函数 4、莫比乌斯函数性质-定理2 定理2：设f(n)和 F(n)均为定义在N上的数论函数， 那么F(n)为f(n)的莫比乌斯变换，即 的充要条件是 这里， 为莫比乌斯函数， * 注：因d遍历n的所有因子，当且仅当， n/d遍历n的 所有因子。因此f(n)也可写 预备 对于 k|(n/d)，指有整数q使得n/d=kq，即n=
8、dkq 即d|(n/k)，d|n * 证明 必要性： 设 成立，那么 * 证明 充分性： 设 成立，那么 令d=km，那么 * 3个特例之1、2 1. 设f1(n)=n，那么 为n的所有正 因子之和。 如设 ，那么 F1 (n)= 根据反演公式有 2. 设f2(n)=1，那么 为n的所有 正因子个数(1+1)(2+1) (k+1)。 有类似反演公式，很神奇。 * * 3个特例之3 3. 若f(n)是欧拉函数(n)，则 反演后 莫比乌斯变换的另一种有用形式 设f(n)，F(n)为整数函数，1n,dN。记 那么有 证明：以下假定：n, dN 记 有 证明 归类合并 证明 这里利用了 5、莫比乌斯函
9、数应用- Eratosthenes筛法 设A=为整数序列（可重复），记d为 正整数， Ad= ， 用|Ad|记序列Ad中元素的个数。 举例： 如A=，d=3，那么 A3=，元素个数为5. A7=，元素个数为3. * 定理3、Eratosthenes筛法 定理3、设m为正整数， p1,p2,pt为m的所有不同 的素因子。那么 序列A中与m既约的整数的个数为 证明：已有结论 特别地， 因此 * 举例-求不超过120的素数的个数 解：不超过120的合数必是2、3、5或7的真倍数。记 m=2*3*5*7=210，记A=1.120，d|210，记Ad= a： d | a ，0a121，|Ad|=120/
10、d * d1235761014152135304270105210 (d)1-1-1-1-1111111-1-1-1-11 |Ad| 120 60 4024172012885342110 1到120中与120既约的整数的个数为 =120-60-40-24-17+(20+12+8+8+5+3)-4-2-1-1 =120-141+56-8=27，而2、3、5、7虽与120不既约，但是素数 。1不是素数。因此不超过120的素数的个数=27+4-1=30 容斥原理与莫比乌斯变换对照 两个集合的容斥关系公式： AB =|AB| = |A|+|B| - |AB |(：重合的部分） 三个集合的容斥关系公式：
11、 |ABC| = |A|+|B|+|C| - |AB| - |BC| - |CA| + |ABC| 一般地，设S为有限集，AiS，则 * 思考 在1到1000的自然数中，能被3或5整除的数共有多少个？ 不能被3或5整除的数共有多少个？ 解：略 分母是1001的最简分数一共有多少个？ 分析：这一题实际上就是找分子中不能与1001进行约分的 数。由于1001=71113，所以就是找不能被7，11，13整 除的数。 由容斥原理知：在11001中，能被7或11或13整除的数有 （143+91+77）-（13+11+7）+1=281（个），从而不能被7 、11或13整除的数有1001-281=720（个
12、）.也就是说，分母 为1001的最简分数有720个。 * 定理3推论 推论：设m为正整数，那么 序列A中使gcd(m, a)=k 的整数的个数为 * 序列A的几种常见形式 设A为整数的一个序列，m为正整数。那么 1. 设n为正整数，A为1到n的自然数的序列。那么 Ad=，|Ad|=n/d 那么1到n中与m互质的自然数的个数为 特别地， 1到n中与n互质的自然数的个数为 * 可用于求1到n中素数个数 序列A的几种常见形式 2. 设n为正整数，A为1到n的所有自然数对(a, b)的 gcd序列，即 A=，A 共有n2个元素， Ad=，显然 |Ad|=n/dn/d A中与m互质的自然数的个数为 3.
13、 设A为1到n的所有自然数对(a, b,c)的gcd序列，那 么 |Ad|=n/dn/dn/d。A中与m互质的自然数 的个数为 * 注意：有许多重复的 例1、公因数为质数问题 问题描述：给一个正整数n，其中n=107，求使得gcd(x,y)为 质数的(x,y)的个数，（1=x,y=n）。 分析： 要使得一个数gcd(x,y)为质数，可枚举小于等于n的质数p， 那么对于每一个质数，只需要考虑在区间1,n/p中，满足序 对 (x,y)互质的对数。 不妨设xy，那么如果枚举每一个y，小于y有多少个x与y互 素，这正是欧拉函数，即(y)。 所以可用递推法求欧拉函数，将得到的答案乘以2即可。但 还有漏计
14、算的，即x=y且y为素数的情况，再加上就行了。 参考代码见下页。 * #include #include using namespace std; typedef long long LL; const int N = 10000010; bitset prime; LL phiN, fN; int pN, k; void isprime() /求素数组 k = 0; prime.set(); for(int i=2; iN; i+) if(primei) pk+ = i; for(int j=i+i; jN; j+=i) * primej = false; void Init() /求(i) int i,j; for( i=1; i= 1; for( i=3; iN; i+=2) if(phii = i) for(
