NOIP数论.pptx

,2013/10/26,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,数学,素数和整除问题,素数筛法,O(NlogN),算法不再赘述,介绍一种,O(N),算法：,将,i,从,2,到,N,扫描,从前,i,未被筛过则存入,prime,数组,用,j,从,1,循环，用,i*primej,筛素数，若,i mod primej=0,跳出,不难发现，每个合数被删仅一次,x=ak1*bk2(a,b,为素数,ab),i=a(k1-1)*bk2,primej=a,时,x,被筛去,复杂度为,O(N),for(i=2;i=n;i+),if(!hashi),prime+tot=i;,for(j=1;primej*i=b,，则,Gcd(a,b)=,Gcd(a/2,b/2)*2 a%2=0 b%2=0,Gcd(a,b/2)a%2=1 b%2=0,Gcd(a/2,b)a%2=0 b%2=1,Gcd(b,a-b)a%2=1 b%2=1,为什么是,log,级别的？,素数和整除问题,(NOIp 2009),已知,Gcd(x,a,0,)=a,1,Lcm(x,b,0,)=b,1,求满足条件的,x,个数,(a,0,a,1,b,0,b,1,=k,a,1,否则,k,x,=k,a,1,若,k,b,0,=k,b,1,则,k,x,bx+(a-a/b*b)y=c,xa+yb=c -ya+(x-a/b*y)b=c,回溯时令,x=y y=x-a/b*y,扩展欧几里得,代码求,ax+by=gcd(a,b),#include,int extended_gcd(int a,int b,int*x,int*y),int ret,tmp;,if(!b),*x=1;,*y=0;,return a;,ret=extended_gcd(b,a%b,x,y);,tmp=*x;,*x=*y;,*y=tmp-a/b*(*y);,return ret;,int main(),int a,b,x,y,z;,scanf(%d%d,z=extended_gcd(a,b,printf(%d%d%dn,z,x,y);,system(pause);,return 0;,扩展欧几里得,求解,ax+by=c?,判断,c,是否被,gcd(a,b),整除，整除则有解，反之无解,求解,ax+by=gcd(a,b),若,ax+by=gcd(a,b),的解为,(x,y),则,ax+by=c,的解,(x,y)=(c/gcd(a,b)*x,c/gcd(a,b)*y),如何求出不定方程的所有整数解？,(x+k*b/gcd(a,b),，,y-k*a/gcd(a,b),为所有合法解,其中,kZ,简单排列组合计数,排列与组合,排列数：,N,个不同物体不重复地取,M,个做排列的方法数,P(N,M)=N!/(N-M)!,组合数：,N,个不同物体不重复地选取,M,个的方法数,C(N,M)=N!/(N-M)!*M!),可重排列：,K,种元素，重数分别为,n1,n2,nk,，所有,n=ni,个元素的全排列数为,n!/(n1!n2!.nk!),K,种元素，重数均为无限大，选取,r,的的组合数为,C(r+K-1,r),可以转化为矩阵内从左上角到右下角只能向右走或下走的方法数问题,排列组合,组合公式的推论,c(n,m)=c(n,n-m);c(n,m)=c(n-1,m-1)+c(n-1,m),卡特兰数,h(n)=C(2n,n)/(n+1)(n=0,1,2,.),错排公式,递推式：,M(n)=,(,n-1,),M(n-2,),+M(n-1,),特殊地，,M=0,M=1,错排公式为,M(n)=n!(1/2!-1/3!+.+(-1)n/n!),容斥原理,研究有限集合的,交或并,的计数,。,DeMorgan,定理 论域,U，,补集,有,容斥原理,(,a,),(,b,),DeMogan,定理的推广：设,容斥原理,容斥原理,最简单的计数问题是求有限集合,A,和,B,的并的元素数目。显然有,即具有性质,A,或,B,的元素的个数等于,具,有性质,A,和性质,B,的元素个数,(,1,),定理,：,定理：,设,是有限集合，则,(,4,),容斥原理,(,5,),容斥原理指的就是（,4,）和（,5,）式。,容斥原理,例4。,求不超过120的素数个数。,例,因 ，故不超过120的合数必然是2、3、5、7的倍数，而且不超过120的合数的因子不可能都超过11。,设 为不超过120的数 的倍数集，,=2，3，5，7。,例,例,例,例,注意：,27并非就是不超过120的素数个数，因为这里排除了2，3，5，7着四个数，又包含了1这个非素数。2，,3，5，7本身是素数。故所求的不超过,120的素数个数为：,27+4-1=30,例,向量,需要注意的细节,常用头文件,#include,计算几何中一般来说使用,double,型比较频繁，请注意数据类型的选择，该用实数的时候就用,double,，而,float,容易失去精度。,判断,double,型的,x,是否为,0,，应当用,x-eps,（或者,fabs(x)eps,），其中,eps,代表某个精度，常常取,eps=0.000001,，还有其他类似情况也要注意,double,类型的精度问题，,int(x+eps),，避免,x=4.999999999,需要注意的细节,圆周率取,3.141592654,或者更精确，或者用,acos(-1),角度制和弧度制的转换，,C/C+,中的三角函数均为弧度制,尽量少用除法，开方，三角函数，容易失去精度。用除法时注意除数不为,0,输出的时候要小心,-0.00000,，比如,a=-0.0000001,，,printf(“%.5lf”,a);,向量及其运算,计算几何中经常使用向量，而且基本上都是二维的，下面用,代表三个向量,=(x0,y0)=(x1,y1)=(x2,y2),某些题目需要经常使用向量运算，因此对于这类问题最好建立构造类型或者类来表示向量，并将向量之间的运算进行重载,一般需要重载加法，减法，和向量乘法,向量及其运算,struct point /,构造点的数据类型，也可作向量使用,double x;,double y;,v1,v2;,point operator+(point p1,point p2);,double operator*(point p1,point p2);,向量及其运算,加法,=,+=,（,x0+x1,y0+y1,）,满足平行四边形法则,图形表示,减法图形表示,向量及其运算,向量有两种乘法，内积（数量积，点积）和外积（向量积，叉积），一般是要根据题目需要选择其中一个重载，多数情况是重载外积，其中,内积,=x0*x1+y0*y1,外积,=x0*y1 x1*y0=,向量及其运算,内积的几何意义：,在,的投影,与,的长度乘积,外积的几何意义：,和,所张成的平行四边形的有向面积,外积在计算几何的题目当中经常使用,外积的应用,判断外积的符号，右手定则,如图，,0,如果,=0,则等价于两个向量共线（同向或反向），可以用此判断三点共线问题。当然，这里的,=0,在实际编程的时候要用一个精度来控制,外积的应用,利用外积求三角形面积,已知三个顶点坐标为,(a0,b0),(a1,b1),(a2,b2),，则三角形面积为注意别忘记取绝对值，这里利用面积是否为,0,也可以考察三点共线问题,这个方法求面积比海伦公式或者其他方法要好,外积的应用,由求三角形面积的方法可以推广求凸多边形面积,如图，从一固定点出发，向其他各点引辅助线，这样就分割成了若干个三角形，利用上式求出每个三角形的面积再相加即可。,整点多边形,整点多边形是指顶点的横纵坐标均为整数,由外积导出的面积计算公式可以看出，整点多边形的面积或为整数，或为整数,/2.,Pick,公式：整点多边形的面积,=,内部整点个数,+,边上的整点个数,/2-1.,NKOJ 1159:Triangle,计算几何中的公式有不少，需要积累,三角形的一些性质,如何判断点是否在三角形内部？,此点与三角形三个顶点相连，出现三个三角形，如果这三个三角形的面积之和等于原三角形面积，那么该点在内部,推广：可用来判断点是否在凸多边形,内部,判断点在直线上,利用三点共线的等价条件,=0,直线上取两不同点,P1,P2,，若点,P,在直线上，则,fabs(P1-P)(P2-P)eps,如果该题目需要编写求三角形面积的函数，那直接判断这三个点形成的三角形面积是否,eps,判断点在线段上,判断点,P(x,y),是否在线段,P1P2,上，其中,P1(x1,y1),P2(x2,y2),需要验证两条,（,1,）点,P,在,P1P2,所在直线上，即三点共线,（,2,）点,P,在,P1P2,为对角线的矩形内,其中（,2,）利用,min(x1,x2)=x=max(x1,x2)&min(y1,y2)=y=max(y1,y2),用高斯消元法,解线性方程组,线性方程组的一般形式,a,1,1,x,1,+a,1,2,x,2,+a,1,n,x,n,=b,1,a,2,1,x,1,+a,2,2,x,2,+a,2,n,x,n,=b,2,a,n,1,x,1,+a,n,2,x,2,+a,n,n,x,n,=b,n,下面是,n,元线性方程组的一般形式：,我们可以把它表示为增广矩阵的形式：,a,1,1,a,1,2,a,1,n,b,1,a,2,1,a,2,2,a,2,n,b,2,a,n,1,a,n,2,a,n,n,b,n,先看一个例子,2,-1,3,1,4,2,5,4,1,2,0,7,2,-1,3,1,4,-1,2,2.5,-1.5,6.5,2,-1,3,1,4,-1,2,-0.875,5.25,2 0.5,0.625,得出：,x,3,=5.25/(-0.875)=-6,x,2,=(2-(-1)x,3,)/4=-1,x,1,=(1-(-1)x,2,-3x,3,)/2=9,消元过程,a,1,1,(1),a,1,2,(1),a,1,n,(1),b,1,(1),a,2,1,(1),a,2,2,(1),a,2,n,(1),b,2,(1),a,n,1,(1),a,n,2,(1),a,n,n,(1),b,n,(1),注：用上标(,k),表示第,k,次消元前的状态,第1次消元，第1行的乘数：,（,i=2,3,n,）,a,1,1,(1),a,1,2,(1),a,1,n,(1),b,1,(1),a,2,2,(2),a,2,n,(2),b,2,(2),a,n,2,(2),a,n,n,(2),b,n,(2),得到新的增广矩阵：,a,i,j,(2),=a,i,j,(1),-m,i,1,a,1,j,(1),b,i,(2),=b,i,(1),-m,i,1,b,1,(1),（,i,j=2,3,n,）,第,k,次消元，第,k,行的乘数：,（,i=k+1,k+2,n,）,消元过程,a,1,1,(1),a,1,2,(1),a,1,n,(1),b,1,(1),a,2,2,(2),a,2,n,(2),b,2,(2),a,k,k,(k),a,k,n,(k),b,k,(k),a,n,k,(k),a,n,n,(k),b,n,(k),第,k,次消元前的增广矩阵：,a,i,j,(k+1),=a,i,j,(k),-m,i,k,a,k,j,(k),b,i,(k+1),=b,i,(k),-m,i,k,b,k,(k),增广矩阵的变化：,（,i,j=k+1,k+2,n,）,第,k,步消元的主行,第,k,步消元的主元素,回代过程,a,1,1,(1),a,1,2,(1),a,1,n,(1),b,1,(1),a,2,2,(2),a,2,n,(2),b,2,(2),a,n,n,(n),b,n,(n),最后得到的增广矩阵：,最终结果的计算：,为什么要选主元素,前面介绍的消元法都是按照自然顺序，即,x,1,、,x,2,、,、,x,n,的顺序消元的。有：,所以每一次消元的主元素都不能为0。如果按照自然顺序消元的过程中出现的,a,k,k,(k),=0,，,那么消元无法继续进行下去。或者|,a,k,k,(k),|很小，也会严重影响计算精度。,为什么要选主元素,例如（假设运算过程中使用单精度实数）：,10,-10,11,112,10,-10,11,-10,10,-10,10,解得：,x,1,=0,，,x,2,=1,这个解与第二个方程差异很大。究其原因，因为消元过程中第一个方程所乘的系数过大，使得上式“吃掉”了下式，所以在结果中根本无法体现下式。,但如果调整一下顺序：,112,10,-10,11,112,11,解得：,x,1,=1,，,x,2,=1,，,这个解基本符合原方程,所以每次消元的主元素的绝对值应该尽可能大，使得与主行相乘的乘数尽可能小。,选主元素,a,1,1,(1),a,1,2,(1),a,1,n,(1),b,1,(1),a,2,2,(2),a,2,n,(2),b,2,(2),a,k,k,(k),a,k,n,(k),b,k,(k),a,l,k,(k),a,l,n,(k),b,l,(k),a,n,k,(k),a,n,n,(k),b,n,(k),进行第,k,次消元时，将,a,k,k,与以,下,各元素（包括,a,k,k,）,进行比较，将其中的最大者所在行与第,k,行交换。,无解的情况,如果在消元的过程中，增广矩阵出现这样一行：左侧各未知数的系数都为0，而右侧的常数项不为0，则意味着方程组无解。,无数组解的情况,在消元过程中，出现这样一行：各未知数的系数和常数项都为0。这相当于少了一个方程，也就是接下来的消元过程中，方程的个数少于未知数的个数，方程要么无解，要么有无数组解。下面讨论对于这样的方程，如何得到一组解。先看这样一个方程：,4,2,3,9,2,1,1,4,2,1,2,5,4,2,3,9,0,0,-0.5,-0.5,00,0.5,0.5,如果继续消元（消第2列），必须保证,a,2,2,0,，,可是第2列中不存在非0的项。,无数组解的情况,4,2,3,9,0,0,-0.5,-0.5,00,0.5,0.5,只能够把第3列的元素作为第2次消元的主元素，进行消元,：,4,2,3,9,0,0,-0.5,-0.5,00,0,0,第2次消元得到的元素全部为0，所以第三行元素已失去意义。,x,2,没有做过主元素，可随意取值，再进行回代，得到一组可行解。如令,x,2,=0,，,x,3,=1,，,x,1,=1.5,。,对于一般的线性方程组，先进行消元，每次消元前找到系数不完全为0的列，相应的元素作为此次消元的主元素，直至第,k,次消元时，得到的新元素全部为0，这时把各未知数分为两种：第,k+1,列至第,n,列对应的未知数，可以将这些未知数随意取值；第1列至第,k,列对应的未知数，这些未知数的值在回代过程中确定。,性能分析,时间复杂度：,O(n,3,),消元,O(n,3,),选主元素：,O(n,2,),回代,O(n,2,),空间复杂度：,O(n,2,),增广矩阵,O(n,2,),如使用全选主元素，还需一个存储列与元素对应信息的表，为,O(n),精度：,由于采用实数运算，另外每一次（第一次除外）消元都要使用以前消元产生的结果，每一次回代都要使用消元结果和其它回代结果，所以累积误差比较严重，该方法只能够求得近似解。但是可以根据具体需要进行相应改进。,整数线性方程组的精确解法,前面讨论了对于一般线性方程组通过实数运算得到近似解的算法。而在一些问题中，常常要求精确解，这里讨论一下系数、常数项和解均为整数的线性方程组的精确解法。,前面是用这种方法消元的：,a,i,j,(k+1),=a,i,j,(k),-m,i,k,a,k,j,(k),b,i,(k+1),=b,i,(k),-m,i,k,b,k,(k),显然这里进行的是实数运算。,整数线性方程组的精确解法,由于不能够保证,ai,k(k),是,ak,k(k),的倍数，要想消元，必须使两行分别乘以一个乘数。,a,i,j,(k+1),=m,i,k,a,i,j,(k),-m,i,k,a,k,j,(k),b,i,(k+1),=m,i,k,b,i,(k),-m,i,k,b,k,(k),方程较多时，系数有可能越来越大，到一定程度有可能导致系数越界，因此要随时对各行化简，即把这一行中所有元素除以这些元素的最大公约数。,但是，无论如何，这也保证不了不会发生越界，因此这种算法一般适用于系数、未知数范围较小，未知数个数较少的方程。,异或方程组,异或方程组就是形如这个样子的方程组：,M00 x0M01x1M0N-1xN-1=B0M10 x0M11x1M1N-1xN-1=B1MN-10 x0MN-11x1MN-1N-1xN-1=BN-1,其中“,”,表示异或,(,XOR,exclusive or)，Mij,表示第,i,个式子中,xj,的系数，是,1,或者,0,。,Bi,是第,i,个方程右端的常数，是,1,或者,0,。,异或方程组,解这种方程可以套用高斯消元法，只须将原来的加减操作替换成异或操作就可以了，两个方程的左边异或之后，它们的公共项就没有了。,异或方程组,考虑系数矩阵，每行是一个方程，每列是一个未知数在各个方程中的系数（将第,i,行的方程的所有系数状压到一个数,ai,里）。,我们分析一下消元之后各个方程系数的状况：,由于我们每次选择最大的一个,ai,，并且找到它最高位上的,1,，把其它,所有方程（包含当前行以上的方程）这一位的系数全部消去，也就,是说对于每个方程，它的系数,ai,最高位上的,1,所在的那一列，仅有这一个,1,，其余的都是,0,。,Why,？,异或方程组,再进一步，如果方程个数,n,足够多的话，那么消元之后系数矩阵的每,一行仅有一个,1,，并且这个,1,所在的那一列也仅有这一个,1,。,异或方程组,例题：从,N,个数中选出任意个数，使,XOR,和最大,这,n,个数看做二进制数，第,i,个数的每一位都作为第,i,个方程的系数（也就是上面的,a,数组），然后用上面的方法高斯消元，最后把消元之后的,a,数组全都,xor,起来就是答案。,