第八讲 ACM数论问题.ppt

Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,工大,ACM,团队,*,Click to edit Master title style,湖南工业大学,ACM,数论问题,数论基本知识,信息学竞赛和程序设计竞赛中常考的数论知识关于素数和整,除，关键在于灵活应用,整除,:,如果,a,和,b,是整数，,a0,，若有整数,c,使,b,ac,，就说,a,整除,b,。在,a,整除,b,时，记,a,是,b,的一个因子，,b,是,a,的倍数。用符号,ab,表示,a,整除,b,，,a,不能整除,b,记为,a b,。,整除基本性质有：,（,1,）若,ab,，,ac,，则,a,（,b,c,）,（,2,）若,ab,，则对所有整数,c,，,abc,（,3,）若,ab,，,bc,，则,ac,（传递性）,数论基本知识,素数（,prime,）和合数（,compound,），如果一个整数,p,只有,1,和,p,两个因子，则,p,为素数，不为素数的其它数为合数。,如果,n,为合数，则,n,必有一个小于或等于,n,的平方根的数因子。,给出一个数,n,，如何判断它是不是素数？,朴素的判别法 从,2,开始试除小于,n,的所有自然数，时间复杂度为,O(n,).,如果,a,是,n,的因子，那么,n/a,也是,n,的因子，所以如果,n,有一个大于,1,的真因子，则它必有一个不大于,n,1/2,的因子，时间复杂度,O(n,1/2,),。,算术基本定理：每个正整数都可以唯一地表示成素数的乘积。其中素数因子从小到大依次出现。,最大公约数,gcd(a,b),最小公倍数,lcm(a,b),ab,gcd(a,b)lcm(a,b),如果,gcd(a,b)=1,，则,a,与,b,互素。,工大,ACM,团队,素数算法,最一般的求解,n,以内素数的算法。复杂度是,o(n,*,sqrt(n,),，适合,n,很小,num=0;,for(i=2;i=n;i+),for(j,=2;j,sqrt(i,),primenum,+=i;,工大,ACM,团队,素数,当,n,很大的时候，比如,n=10,000,000,时，,n*,sqrt(n,)30,000,000,000,数量级相当大,思考如何改进？,工大,ACM,团队,素数筛法,最简单的素数筛法,开一个大的,bool,型数组,prime,，大小就是,n+1,就可以了,.,先把所有的下标为奇数的标为,true,下标为偶数的标为,false.,把奇数的倍数设为,false.,见代码,-,prime_choice.c,改进的素数筛法,bool,型数组里面只存奇数不存偶数。如定义,primeN,则,0,表示,3,，,1,表示,5,，,2,表示,7,，,3,表示,9.,。如果,prime0,为,true,则表示,3,时素数。,prime3,为,false,意味着,9,是合数，每个单元代表的数是,2*i+3,。,欲求,n,以内的素数，就先把,sqrt(n,),内的素数求出来，用已经求得的素数来筛出后面的合数。,工大,ACM,团队,数论基本知识,如何求出,1,n,中的所有素数？,Eraosthenes,（爱拉托斯尼筛法）筛法：每次求出一个新的素数，就把,n,以内的它的所有倍数都筛去。,经典的,Eraosthenes,筛法：,for(,int,i=2;i*i N;i+)if(,tagi,)continue;for(,int,j=i;i*j N;j+),tagi,*j=1;for(,int,i=2;i N;i+)if(!,tagi,),primetol,+=i;,一种线性筛素数的方法（复杂度是,O(n,),）：,void,get_prime,(),int,cnt,=0;for(,int,i=2;i N;i+)if(!,tagi,),pcnt,+=i;for(,int,j=0;j,cnt,&,pj,*i N;j+),tagi,*,pj,=1;if(i%,pj,=0)break;/,可以用均摊分析的方法来分析算法的复杂度,由于每,个合数都唯一的被它的最小素因子筛一次，而每个合,数的最小素因子都是唯一的，总复杂度是,O(n,),Eraosthenes,筛法的速度并不快，原因在于对于一个合数，这种方法会重复的标记,工大,ACM,团队,伪素数,同余：,ab(mod,m),如果两个数,a,和,b,之差能被,m,整除，那么我们就说,a,和,b,对模数,m,同余。比如，,100-60,除以,8,正好除尽，我们就说,100,和,60,对于模数,8,同余。它的另一层含义就是说，,100,和,60,除以,8,的余数相同。,a,和,b,对,m,同余，我们记作,ab(mod,m),。比如，刚才的例子可以写成,10060(mod 8),。你会发现这种记号到处都在用，比如和数论相关的书中就经常把,a mod 3=1,写作,a1(mod 3),。,工大,ACM,团队,伪素数,同余：,ab(mod,m),如果两个数,a,和,b,之差能被,m,整除，那么我们就说,a,和,b,对模数,m,同余。比如，,100-60,除以,8,正好除尽，我们就说,100,和,60,对于模数,8,同余。它的另一层含义就是说，,100,和,60,除以,8,的余数相同。,a,和,b,对,m,同余，我们记作,ab(mod,m),。比如，刚才的例子可以写成,10060(mod 8),。你会发现这种记号到处都在用，比如和数论相关的书中就经常把,a mod 3=1,写作,a1(mod 3),。,伪素数：它满足费马小定理，但其本身却不是素数。最小的伪素数是,341,。事实上，费马小定理给出的是关于素数判定的必要非充分条件。若,n,能整除,2(n-1)-1,，并,n,是非偶数的合数，那么,n,就是伪素数。第一个伪素数,341,是萨鲁斯在,1819,年发现的。,费马尔小定理：若,n,是素数，且,a0,则,a,n-1,1(mod n),或,a,n-1,mod n=1,即,(a,n-1,-1)/n=0,2(5-1)-1=15,15|5.2(3-1)-1=3,3|3.,但很多都是素数，如,3,，,5,，,7,，,29,，,31 1819,年数学家萨鲁斯找到了反例：,2(341-1)-1|341,而,341=11*31,是合数，,341,就成了第一个伪素数。以后又发现了许多伪素数：,561 645 1105 1387 1729,工大,ACM,团队,伪素数,伪素数的一个用途,利用伪素数表来判定一个奇数,n,是否为素数。,如果,n,不能整除,2(n-1),1,，则据费马小定理知，,n,必为合数；,如果,n,能整除,2(n-1),1,，且,n,在伪素数表中，则,n,为合数，否则为素数。,这种方法的关键就在于按伪素数表去掉伪素数，而这要求伪素数在能整除,2(n-1),1,的数中相当少才行，这就是当,n,整除,2(n-1),1,时，,n,是合数的比例问题。,在前,10,亿个自然数中，共有,50847534,个素数，而只有以,2,为底的伪素数,5597,个，即在此范围内,n,整除,2n-1,1,产生合数的可能性只有,0.011%,。在,10,亿之内，,n,整除,2(n-1),1,同时整除,3(n-1),1,的合数,n,只有,1272,个，即此时产生合数的可能性只有,0.0025%,。,工大,ACM,团队,Miller-,Rabbin,测试,如果,n,是一个正整数，如果存在和,n,互素的正整数,a,满足,an-11(mod n),，我们说,n,是基于,a,的伪素数。如果一个数是伪素数，它几乎肯定是素数。,function Miller-,Rabbin(n:longint):boolean,;,begin,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;,工大,ACM,团队,大数的素性判断,对于大数的素性判断，目前,Miller-Rabin,算法应用最广泛。,一般底数仍然是随机选取，但当待测数不太大时，选择测试底数就有一些技巧了。,比如，如果被测数小于,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,算法在,OI(,信息学奥林匹克竞赛,),中非常实用。通常认为，,Miller-Rabin,素性测试的正确率可以令人接受，随机选取,k,个底数进行测试算法的失误率大概为,4(-k),。,伪素数：如果,n,是一个正整数，并且存在和,n,互素的正整数,a,满足,a,n-1,1(mod n),我们说,n,是基于,a,的伪素数。如果一个数是伪素数，它几乎肯定是素数。另一方面，如果一个数不是伪素数，它一定不是素数。,工大,ACM,团队,HDOJ_1108,最小公倍数,给定两个正整数，计算这两个数的最小公倍数。,10 14,70,工大,ACM,团队,欧几里德算法,int gcd(int da,int xiao),int temp;,while(xiao!=0),temp=da%xiao;,da=xiao;,xiao=temp;,return(da);,思考：,递归的形式如何写？,工大,ACM,团队,扩展的欧几里德算法,对于不完全为,0,的非负整数,a,，,b,，,gcd,（,a,，,b,）表示,a,，,b,的最大公约数，必然存在整数对,x,，,y,，使得,gcd,（,a,，,b,）,=,ax+by,。如果,gcd(a,b),d,，那么一定存在,x,，,y,满足,ax,by,d,。,扩,展欧几里得算法其实是解二元一次不定方程的算法,Function,extended_gcd(a,b:longint,;,Var,x,y:longint):longint,;,Begin,if b=0 then begin,extended_gcd,:=a;,x:=1;,y:=0;,end else begin,extended_gcd,:=,extended_gcd(b,a mod b);,t:=x;,x:=y;,y:=t-(a div b)*y;,end;,End;,工大,ACM,团队,扩展的欧几里德算法,求解,x,，,y,的方法的理解,设,ab,。,1,，显然当,b=0,，,gcd,（,a,，,b,）,=a,。此时,x=1,，,y=0,；,2,，,ab,0,时,设,ax1+by1=,gcd(a,b,);,bx2+(a mod b)y2=,gcd(b,a,mod b);,根据朴素的欧几里德原理有,gcd(a,b,)=,gcd(b,a,mod b);,则,:ax1+by1=bx2+(a mod b)y2;,即,:ax1+by1=bx2+(a-(a/b)*b)y2=ay2+bx2-(a/b)*by2;,根据恒等定理得：,x1=y2;y1=x2-(a/b)*y2;,这样我们就得到了求解,x1,y1,的方法：,x1,，,y1,的值基于,x2,，,y2.,工大,ACM,团队,扩展的欧几里德算法,int,exGcd(int,a,int,b,int,&x,int,&y),if(b,=0),x=1;,y=0;,return a;,int,r=,exGcd(b,a%b,x,y);,int,t=x;,x=y;,y=t-a/b*y;,工大,ACM,团队,扩展的欧几里德算法的应用,POJ 1061-,青蛙的约会,两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。可是它们出发之前忘记了一件很重要的事情，既没有问清楚对方的特征，也没有约定见面的具体位置。不过青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上，不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙，你被要求写一个程序来判断这两只青蛙是否能够碰面，会在什么时候碰面。我们把这两只青蛙分别叫做青蛙,A,和青蛙,B,，并且规定纬度线上东经,0,度处为原点，由东往西为正方向，单位长度,1,米，这样我们就得到了一条首尾相接的数轴。设青蛙,A,的出发点坐标是,x,，青蛙,B,的出发点坐标是,y,。青蛙,A,一次能跳,m,米，青蛙,B,一次能跳,n,米，两只青蛙跳一次所花费的时间相同。纬度线总长,L,米。现在要你求出它们跳了几次以后才会碰面。,工大,ACM,团队,POJ 1061,输入只包括一行,5,个整数,x,，,y,，,m,，,n,，,L,，其中,xy,2000000000,，,0 m,、,n 2000000000,，,0 L 2100000000,。,输出碰面所需要的跳跃次数，如果永远不可能碰面则输出一行,Impossible,工大,ACM,团队,POJ 1061,Input,输入只包括一行,5,个整数,x,，,y,，,m,，,n,，,L,，其中,xy,2000000000,，,0 m,、,n 2000000000,，,0 L 2100000000,。,Output,输出碰面所需要的跳跃次数，如果永远不可能碰面则输出一行,Impossible,Sample Input,1 2 3 4 5,Sample Output,4,工大,ACM,团队,解题思路,此题其实就是扩展欧几里德算法求解不定方程，线性同余方程。,设过,s,步后两青蛙相遇，则必满足以下等式：,(,x+m,*,s)-(y+n,*s)=k*,l(k,=0,1,2.),稍微变一下形得：,(,n-m,)*,s+k,*l=,x-y,令,n-m,=,a,k,=,b,x-y,=c,即,a*,s+b,*l=c,只要上式存在整数解，则两青蛙能相遇，否则不能。,首先想到的一个方法是用两次,for,循环来枚举,s,l,的值，看是否存在,s,l,的整数解，若存在则输入最小的,s,，但显然这种方法是不可取的，谁也不知道最小的,s,是多大，如果最小的,s,很大的话，超时是明显的。,工大,ACM,团队,解题思路,求,a*x+b*y=n,的整数解。,1,、先计算,Gcd(a,b,),，若,n,不能被,Gcd(a,b,),整除，则方程无整数解；否则，在方程两边同时除以,Gcd(a,b,),，得到新的不定方程,a*x+b*y=n,，此时,Gcd(a,b,)=1;,2,、利用上面所说的欧几里德算法求出方程,a*x+b*y=1,的一组整数解,x0,y0,，则,n*x0,n*y0,是方程,a*x+b*y=n,的一组整数解；,3,、根据数论中的相关定理，可得方程,a*x+b*y=n,的所有整数解为：,x=n*x0+b*t y=n*y0-a*t (t,为整数,),上面的解也就是,a*x+b*y=n,的全部整数解。,工大,ACM,团队,解题思路,此时方程的所有解为：,x=c*k1-b*t,。,x,的最小的可能值是,0,令,x=0,，可求出当,x,最小时的,t,的取值，但由于,x=0,是可能的最小取值，实际上可能,x,根本取不到,0,，那么由计算机的取整除法可知：由,t=c*k1/b,算出的,t,，代回,x=c*k1-b*t,中。,求出的,x,可能会小于,0,，此时令,t=t+1,，求出的,x,必大于,0,；如果代回后,x,仍是大于等于,0,的，那么不需要再做修正。,工大,ACM,团队,核心代码分析,while(scanf(%I64d%I64d%I64d%I64d%I64d,&x,&y,&m,&n,&l)!=EOF),a=n-m;,b=l;,c=x-y;,r=gcd(a,b);,if(c%r),printf(Impossiblen);,continue;,a/=r;b/=r;c/=r;,exgcd(a,b,k1,k2);,t=c*k1/b;,k1=c*k1-t*b;,if(k10),k1+=b;,printf(%I64dn,k1);,工大,ACM,团队,练习题,pku:1006,1014,1023,1061,1152,1183,1730,2262,2356,1811,工大,ACM,团队,