ACM_数论——南开大学.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,Butterfly0923,Doraemonok,jackfeng,2008,年南开大学,ACM,协会暑期集训,数论,二分法,in,乘方,如何计算,a,n,？,1,）计算,a*a*a*,*a*a*a,，需要计算,n-1,次乘法，时间复杂度,O(n),2,）考虑实例,a4,，计算,b=a*a,，再算,c=b*b,，则,c=a4,，但是只用了两次乘法，效率提高。比如,a9=a*(a4)*(a4),，只需用,4,次乘法，一般的，,an,时间复杂度为,O(logn),二分法,in,乘方,第二种算法与二进制的关系,9=(1001),2,，,a9=a8*a;,10=(1010),2,，,a10=a8*a2;,从二进制最后一位开始，如果第,k,位是,1,，就乘以,a(2(k-1),计算每个,a(2k),需要,logn,，得到答案最多需要乘,logn,次，所以复杂度是,O(logn),如果把,a,看作矩阵，上面方法可应用于矩阵乘方,（注：这并不是最快的办法，有兴趣的同学可以做一下,poj3134,）,求素数方法,1,）,pN,存储所有的素数，二重循环，用已经求出的不大于平方根的所有素数试除,for(i=2;in;+i),for(j=0;jm+j),如果,pj,整除,i,，则,i,不是素数,如果都不能整除，则,i,是素数，添加到素数列表,pN;,素数,2,）增加布尔型数组,bN,记录是否为素数，初始化所有值,=1,，从头开始遍历，如果,bi=1,，则,i,是素数，将所有的,i,的倍数,j,均修改为,bj=0,for(i=2;in;+i),如果,bi=1,则添加到素数列表,p,，然后利用循环,for(j=i;j,b*x+(a-a/b*b)*y=a*y+b*(x-a/b*y),，所以,a*x+b*y=d,的解,x1=y0,，,y1=x0-a/b*y0;,这样我们可以程序迭代了。,注：,a,b,为正整数，设集合,A,=x*a+y*b|x,y,是整数,，则,A,中最小正元素是,gcd(a,b),费马小定理及其推广,若,p,为素数，,gcd(a,p)=1,则,a(p-1)=1(mod p),推广：,若,gcd(a,n)=1,则,af(a)=1(mod n),其中,f(a),为,a,的欧拉函数，这里注意到，如果,n,为素数，则由于,n,的欧拉函数,=n-1,，可以推出费马小定理,Extended-Euclid,算法,扩展欧几里德算法：,EXTENDED-EUCLID(a,b),if b=0,then return(a,1,0),(d,x,y,)EXTENDED-EUCLID(b,a%b),(d,x,y)(d,yx,(a/b)*y,),return(d,x,y),13,求解模线性方程,定理：方程,ax=b(mod n),对于未知量,x,有解，当且仅当,gcd(a,n)|b,定理：方程,ax=b(mod n),或者对模,n,有,d,个不同的解，其中,d=gcd(a,n),或者无解。,14,求解模线性方程,定理：设,d=gcd(a,n),，假定对整数,x,和,y,，有,d=ax,+ny,。如果,d|b,，则方程,ax=b(modn),有一个解的值为,x,0,，满足,x,0,=x,(b/d)mod n,。,15,求解模线性方程,定理：假设方程,ax=b(mod n),有解（即有,d|b,，其中,d=gcda,n),），,x,0,是该方程的任意一个解，则该方程对模,n,恰有,d,个不同的解，分别为：,x,i,=x,0,+i(n/d)(i=1,2,d-1),。,16,求解模线性方程,MODULAR-LINEAR_EQUATION_SOLVER(a,b,n),(d,x,y,)EXTENDED-EUCLID(a,n),if(d|b),then x0 x,(b/d)mod n,for i 0 to d-1,do print(x0+i(n/d)mod n,else print,“,no solution,”,求解模线性方程组,中国剩余定理的内容如下：令,n=n1n2.nk,，其中,ni,是两两互质的数，则对,0=an,与,0=aini,且,a=ai,mod,ni,首先定义,mi=n/ni(i=1,2.k),，则,mi,是除了,ni,以外的所有,nj,的乘积，由于,GCD(mi,ni)=1,，所以用扩展,Euclid,算法得,ci,满足,bini+cimi=1,a=a1c1m1+a2c2m2+.+akckmk,(mod,n),LCM(Least Common Multiple),有了,GCD,LCM,就好办了,LCM(a,b)=a*b/GCD(a,b),实际上最好写成,a/GCD(a,b)*b,思考：为什么下面的写法好？,其他一些关于约数的公式,若,n=p,1,e1,p,2,e2,p,r,er则,n,的因数个数为,(1+e1)*(1+e2),*,(1+er),n,所有因数的和为,(1+p,1,+p,1,2,+p,1,e1,)*(1+p,2,+p,2,2,+p,2,e2,)*(1+p,r,+p,r,2,+p,r,er,),n!,n!=p1n1*p2n2*,*pknk,勒让德定理：,ni=n/pi+n/pi2+n/pi3+,其中,表示向下取整,欧拉函数,(x),表示与,x,互质且小于,x,的正整数的个数,如果,x,为素数，则欧拉函数等于,x-1,求法：将,x,分解为,p1n1*p2n2*,pknk,，则,欧拉函数,=p1(n1-1)*,*pk(nk-1)*(p1-1)*,*(pk-1),Exercise,NKOJ:,1053:,哥德巴赫猜想,1236:ab,1430:Fibonacci,1249:,分解素因子,1200:Euclids Game,1389:Divisors,1214:Relatives,1379 C Looooooops,1602 Gossiping,POJ:,1061:青蛙的约会,2891:Strange Way to Express Integers,