《[PPT模板]ACM数论.ppt》由会员分享，可在线阅读，更多相关《[PPT模板]ACM数论.ppt（48页珍藏版）》请在三一办公上搜索。
1、1,数论,来自天津大学等学校的培训材料,2,初等数论的概念,整除性和约数：假设d和a是整数，d|a（读作d整除a），意味着存在某个整数k，有a=kd。如果d|a，并且d0，则称d是a的约数。每个整数a都可以被其平凡约数1和a整除，a的非平凡约数也成为a的因子。,3,快速幂,3 999=3(512+256+128+64+32+4+2+1)=(3 512)*(3 256)*(3 128)*(3 64)*(3 32)*(3 4)*(3 2)*3这样只要做16次乘法。即使加上一些辅助的存储和运算，也比直接乘高效得多（尤其如果这里底数是成百上千位的大数字的话）。我们发现，把999转为2进制数：11111
2、00111，其各位就是要乘的数。这提示我们利用求二进制位的算法（其中mod是模运算）：,4,快速幂,NumberType optimized_pow_n(NumberType x,unsigned int n)NumberType pw=1;while(n 0)if(n,5,初等数论的概念,素数和和数对于某个整数a1，如果它仅有平凡约数1和a则称p是素数。否则p是合数。可以证明素数有无限多个。筛法求素数。,6,int vis1000000=1,1;int prime1000000;int prime_count=0;void create_prime(int n)int i,j,m;m=(in
3、t)sqrt(n+0.5);for(i=2;i=m;i+)if(!visi)primeprime_count+=i;for(j=i*i;j=n;j+=i)visj=i;,7,初等数论概念,除法定理，余数和同模除法定理：对任意整数a和任意正整数n，存在唯一的整数q和r，使得a=qn+r，其中0rn。值q称为除法的商，值r=a(mod n)称为除法的余数。根据整数模n所得的余数，可以把整数分成n个等价类。包含整数的模n等价类为：an=a+kn|kZ,8,常见数列,1.Fibonacci数列,0，1，1，2，3，5，8，13，21,9,2.卡特兰数h(1)1,h(0)=1h(n)=C(2n,n)/(
4、n+1)(n=1,2,3,.)3.错排数n个有序的元素应有n！种不同的排列。如若一个排列式的所有的元素都不在原来的位置上，则称这个排列为错排。M(1)=0,M(2)=1 M(n)=(n-1)M(n-2)+M(n-1)给定N个节点，能构成h(N)种不同的二叉树,10,http:/,A number sequence is defined as follows:f(1)=1,f(2)=1,f(n)=(A*f(n-1)+B*f(n-2)mod 7.Given A,B,and n,you are to calculate the value of f(n).1=A,B=1000,1=n=100,000
5、,000,11,方法一 循环出现？方法二 矩阵幂 fn+1 A B fn fn 1 0 fn-1另：http:/poj.org/problem?id=3070,12,初等数论的概念,公约数与最大公约数d是a的约数并且也是b的约数，则d是a和b的公约数。两个不同时为0的整数a和b的最大公约数表示为gcd(a,b)。,13,初等数论的概念,gcd(a,b)的性质：定理：如果a，b是不全为0的任意整数，则gcd(a,b)是a与b的线性组合ax+by:x,yZ中的最小正元素。推论1：对于任意整数a，b，如果d|a并且d|b，则d|gcd(a,b)。推论2：对于所有整数a和b以及任意非负整数n，gcd(
6、an,bn)=n*gcd(a,b)。推论3：对所有正整数n，a和b，如果n|ab并且gcd(a,n)=1，则n|b。,14,初等数论的概念,互质数：如果两个整数a与b只有公因数1，即如果gcd(a,b)=1，则a与b称为互质数。定理：对任意整数a，b和p，如果gcd(a,p)=1且gcd(b,p)=1，则gcd(ab,p)=1。,15,初等数论概念,唯一因子分解唯一质因子分解定理：合数a仅能以一种方式，写成如下的乘积形式：a=p1e1p2e2prer其中pi为素数，p1p2pr，且ei为正整数。因子个数(1+e1)(1+e2)(1+er),16,http:/,例1/n=1/a+1/b(ab)的
7、对数,17,由于a=n+k2*n(如果等于2n那么就是a=b了)得到 kn，而显然k是n2的因子质数打表，利用前面因子个数的结论,18,欧拉函数,欧拉函数是少于或等于n的数中与n互质的数的数目，即和n的最大公约数为1的数字的个数。先因子分解Phi(n)=n*(1-1/p1)*(1-1/p2)*(1-1/pk)推导过程见刘汝佳 算法竞赛入门经典p184,19,初等数论基本概念,例：求一个正整数n的所有约数和。把正整数n分解质因子的乘积，假设结果为n=p1e1p2e2prer，那么正整数n的所有因子之和为：Sum=(1+p1+p12+p1e1)*(1+p2+p22+p2e2)*(1+pr+pr2+
8、prer),20,例：求N!中素因子P的个数我们提取的数字显然是：P*2P*3P，显然有 N/P个提取P,之后我们又得到了 1*2*3*N/P cnt=0;while(N)cnt+=N/p;N/=p;,21,如何分解素因子,通常使用试除法（效率？）得到素数表以后扫描素数表,然后把N的素因子加入解集.对于一个数字N，若想分解它，那么素数表必须筛选到sqrt(N)的级别,22,最大公约数,GCD递归定理：对任意非负整数a和任意正整数b，gcd(a,b)=gcd(b,a mod b)。证明:a可以表示成a=kb+r,则r=a mod b假设d是a,b的一个公约数，则有d|a,d|b,而r=a-kb,
9、因此d|r 因此d是(b,a mod b)的公约数,23,最大公约数,欧几里德算法：又称辗转相除法，用于计算两个整数a，b的最大公约数int euclid(int a,int b)if(b=0)/当 b 减小到 0 时，它们的最大公因数为a return a;else return euclid(b,a%b);,24,最大公约数,欧几里德算法的运行时间引理：如果ab1并且EUCLID(a,b)执行了k1次递归调用，则aFk+2，bFk+1。定理：对任意整数k1，如果ab1且b Fk+1，那么EUCLID(a,b)的递归调用次数少于k次。,25,最大公约数,二进制最大公约数算法：如果a和b都是偶
10、数，那么gcd(a,b)=2gcd(a/2,b/2)。如果a是奇数，b是偶数，那么gcd(a,b)=gcd(a,b/2)。如果a和b都是奇数，那么gcd(a,b)=gcd(ab)/2,b)。,26,扩展欧几里德算法,扩展欧几里德算法是用来在已知a,b的情况下，求解一组x，y使得a*x+b*y=Gcd(a,b)(解一定存在，根据数论中的相关定理)。,27,扩展欧几里德算法原理,Gcd(a,b)=Gcd(b,a%b),可以将a b 的线性组合就化简为 b 与 a%b 的线性组合所以x*a+y*b=Gcd(a,b)=Gcd(b,a%b)=_x*b+_y*a%b=_x*b+_y*(a a/b*b)=_
11、y*a+(_x _y*a/b)*b所以：x=_y y=_x _y*a/b,28,续,根据我们前边的结论：a b 都在减小，当 b 减小到 0 时，我们就可以得出 x=1,y=0然后递归回去就可以求出 最终的 x,y 了,29,实现代码,int ext_gcd(int a,int b,int,30,方程ax+by=c的整数解(a,b,c为整数）,令g=gcd(a,b),很明显,c不是g的倍数时方程无解。如果c等于g，用扩展欧几里德算法求得一组解(x0,y0).如果c是g的倍数，则相应的一组解(x0*c/g,y0*c/g).若方程存在解(x1,y1)，则通解形式为(x1+k*b/g,y1-k*a/
12、g),k为任意整数,31,同余方程（模方程）,同余的概念 a b(mod n)意思是a和b 对n取余的结果相同同余方程 已知a,b,n,求x。a*x b(mod n)ax=b+kn=ax kn=b=ax+(-k)n=b在0,n-1内，ax b(mod n)解的个数为gcd(a,n)即 0=x1+k*n/gcd(a,n)=n-1题目：http:/poj.org/problem?id=2115,32,一个例子,3x 9(mod 10)转化为 3x+10y=9 3x+10y=1 必然有解，通过扩展欧 几里德算法求解，例如求得 x=-3,y=1则3x+10y=9 的一个解为:x=-3*9=-27,y=
13、9那么可以得到x=-27为一个解,于是取模以后得到结果 x 3(mod 10),33,同余方程组与中国剩余定理,孙子算经中，有这样一道算术题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”按照今天的话来说：一个数除以3余2，除以5余3，除以7余2，求这个数.,34,中国剩余定理的原理,设m1,m2,mk是两两互素的正数，则对任意的整数b1,b2,bk,同余方程组X b1(mod m1)意思是X和b1对m1取余的结果相同X b2(mod m2)X bk(mod mk)其解为：,35,续,X=(y1*M1*b1)+(y2*M2*b2)+(yk*Mk*bk)mod m;其中
14、 m=m1*m2*mk;Mi=m/mi;(yi*Mi)mod mi=1 如何求yi因为 Mi 和mi 互质，gcd(Mi,mi)=1必然存在 yi*Mi+xi*mi=1(扩展Euclid),36,x 2(mod 3)x 3(mod 5)x 2(mod 7)X=(y1*35*2+y2*21*3+y3*15*2)mod 105 y1=2 y2=1 y3=1,37,它是怎么实现的？,/bi mi含义见前，k为数组大小int ModularEquations(int b,int m,int k)int i;int d,x,y,a=0,Mi,M=1;for(i=0;ik;i+)M*=mi;for(i=0
15、;ik;i+),38,续,Mi=M/mi;d=ext_gcd(mi,Mi,x,y);a=(a+y*Mi*bi)%M;if(a0)return a;else return(a+M);,39,问题：mi之间不一定互质？,参见http:/,40,素数测试(判断是否素数),要判断一个整数n是不是素数，应用费马定理：如果n是素数，那么对于任意的a都满足an-1=1(mod n)。所以可以通过随机选取若干个a，来检验n是否是素数。如果n是合数，并且满足an-1=1(mod n)那么就说n是一个基为a的伪素数。典型见Carmichael number。,41,Carmichael number,In num
16、ber theory,a Carmichael number is a composite positive integer n which satisfies the congruence for all integers b which are relatively prime to n。前3个Carmichael数是561,1105,1729.Carmichael数是非常少的.在1100000000范围内的整数中,只有255个Carmichael数.,42,对于大数的素性判断，目前Miller-Rabin算法应用最广泛。一般底数仍然是随机选取，但当待测数不太大时，选择测试底数就有一些技巧
17、了。比如，如果被测数小于4 759 123 141，那么只需要测试三个底数2,7和61就足够了。当然，你测试的越多，正确的范围肯定也越大。如果你每次都用前7个素数(2,3,5,7,11,13和17)进行测试，所有不超过341 550 071 728 320的数都是正确的。如果选用2,3,7,61和24251作为底数，那么1016内唯一的强伪素数为46 856 248 255 981。通常认为，Miller-Rabin素性测试的正确率可以令人接受，随机选取 k个底数进行测试算法的失误率大概为4(-k)。,43,function Miller-Rabbin(n:longint):boolean;b
18、egin for i:=1 to s do Begin a:=random(n-2)+2;If modular_exp(a,n-1,n)1 then return false;end;End;return true;End;,44,二次探测定理,二次探测定理 如果p是一个素数,且0 xp,则方程x*x1(mod p)的解为x=1,p-1.事实上,x*x1(mod p)等价于 x*x-10(mod p).由此可知;(x-1)(x+1)1(mod p)故p必须整除x-1或x+1.由p是素数且 0 xp,推出x=1或x=p-1.利用二次探测定理,我们可以在利用费马小定理计算 a(n-1)mod n的
19、过程中增加对于整数n的二次探测.一旦发现违背二次探测条件,即可得出n不是素数的结论.,45,下面的算法power用于计算ap mod n,并在计算过程中实施对n的二次探测.void power(unsigned long a,unsigned long p,unsigned long n,unsigned long,46,修正后的Miller_Rabin,bool Miller_Rabin(unsigned long n,unsigned int k)/重复k次调用 unsigned long a,result;bool composite=false;for(int i=1;i=k;i+)a=Random(n-2)+1;power(a,n-1,n,result,composite);if(composite|(result!=1)return false;return true;,47,Pollard Rho算法-大数的快速分解,见http:/,48,练习题目：,扩展欧几里德算法：POJ 1061 2115中国剩余定理：POJ 1006,
