数论中的程序设计-New.ppt

第,3,次课 数论中的程序设计,沈云付,yfshen,上海大学计算机工程与科学学院,本章主要内容,1,、最大公因数与最小公倍数,2,、求整系数一次不定方程,ax+by=c,的解,3,、求解模线性方程,4,、求模,m,的逆元素算法,5,、模线性方程组与中国剩余定理,6,、模取幂运算与素数测试,7,、实例研究,1,2,3,4,5,6,7,8,9,1,、最大公因数与最小公倍数,公约数和最大公约数的概念,最大公约数的一种求法,分解因子,最大公约数性质与欧几里德转辗相除法,欧几里德转辗相除法,欧几里德算法实现,实例 求最大公因数,问题描述：,从输入文件中读取一组数据，求最大公因数。,输入：,输入有若干行。每一行上有两个整数,x,，,y,，是一组测试数据，他们之间用一个空格隔开。,输出：,对每一组测试数据，每行输出这两个整数的最大公因数。如无最大公因数，则标明,“,no GCD,”,。,输出样例：,(6,11)=1,(0,0)no GCD,(5,0)=5,输入样例：,6 11,0 0,5 0,1,）公因数和最大公因数的概念,公因数：如果,d,是,a,的因数并且也是,b,的因数，则,d,是,a,与,b,的公因数,例：,30,的正因数：,1,，,2,，,3,，,5,，,6,，,10,，,15,、,30,；,24,的正因数：,1,，,2,，,3,，,4,，,6,，,12,，,24,；,24,与,30,的正公因数有：,1,、,2,、,3,、,6,。,1,是任意两个整数的公因数；,最大公因数：两个不同时为,0,的整数,a,与,b,的最大公因数是其值为最大的公因数，记作,gcd(a,b),。,gcd(24,30),6,。,最大公约数的一种求法,分解因子,因为,gcd(a,，,b),gcd(|a|,，,|b|),，所以可考虑非负整数的情况。,通过求因数，可求,a,和,b,的素数因子分解：,a=,，,b=,于是整数,a,和,b,的最大公因数为：,gcd(a,，,b),注意：求一个数的素因子分解问题是,NP,问题。目前用穷举方法可求不太大的整数的整数分解，这种方法不是有效的。只能用优化方法改善计算效率。,最大公因数性质,性质：,（,1,）,gcd(a,，,b),gcd(,a,，,b),（,2,）,gcd(a,，,b),gcd(a+kb,，,b),，,k,为任何整数,（,3,）,gcd(a,，,b),gcd(b,，,a mod b),（,4,）如,a,是非零整数，那么,gcd(a,，,0),|a|,欧几里德转辗相除法的依据：,gcd(a,，,b),gcd(b,，,a mod b),可,求整数,a,和,b,的最大公因数,2,）最小公倍数,公倍数：如果,m,是,a,的倍数并且也是,b,的倍数，那么称,m,是,a,与,b,的公倍数。,最小公倍数：两个非零整数,a,与,b,的最小公倍数是,a,与b,的公倍数中数值最小正的数。,记作,lcm,(,a,，,b,),（或简写为,a,，,b,）。,lcm,(,a,，,b,),lcm,(|,a,|,，,|,b,|),通过,a,和,b,的标准分解，可以求出整数,a,和,b,的最小公倍数：,lcm,(,a,，,b,)=,最小公倍数与最大公因数关系,3,）欧儿里德算法,给定任意两个正整数,a,和,b,gcd(,a,，,b,)=,结论：,求最大公因数的递归程序,用欧几里德转辗相除法构造一个求最大公因数的递归程序。,输入：,非负整数,a,、,b,返回：,a,和,b,的最大公因数,long gcd(long a,long b),long m;,if(b=0)&(a=0)/,表示无最大公因数,return-1;,if(b=0)return a;,else m=gcd(b,a%b,);,return m;,求最大公因数的无递归程序,int gcd(int a,int b),int c;,if(a=0)return b;,while(b!=0)c=b,b=a%b,a=c;,return a;,2,、利用欧几里德算法求整系数一次不定方程,ax+by=c,的解,算法思想：,利用求,a,b,的最大公因数的转辗相除过程，进行多次逆推，使最大公因数的表示式最终表示为,a,与,b,的线性组合,ax,+,by,(,x,与,y,可能为,0,或负数,),。,此时，,d,gcd(,a,b,),做法：将欧几里德算法进行推广，使得该算法不仅能得出任意两个正整数,a,和,b,的最大公因数,d,，而且还能计算出满足下式的整数,x,和,y,：,d,=,ax,+,by,反向递推,辗转相除过程的逆推,记,类似地，记,一般地，,于是有整数,x,和,y,满足：,d,gcd(a,，,b),ax+by,扩展欧几里德算法,-,递归实现,输入整数,a,、,b,，返回,gcd(a,，,b),和对应等式,ax+by=d,中的,x,y,。,long extend_gcd(long a,long b,long&x,long&y),long t,m;,if(b=0)/,表示无最大公因数,ifb=0),x=1;y=0;return a;,else,m=extend_gcd(b,a%b,x,y);,t=x;x=y;y=t-(a/b)*y;,return m;,扩展欧几里德算法,-,无递归实现,int extend_gcd(int a,int b,int*x,int*y),int x0,x1,x2,y0,y1,y2;,int r0,r1,r2,q;,if(a=0)&(b=0),*x=0;*y=0;,return-1;,/gcd(a,b),不存在,if(a=0)&(b!=0),/a=0,时不存在,a,的乘法逆元,*,x=0;*y=1;,return b;,if(b=0)&(a!=0),/b=0,时不存在,b,的乘法逆元,*,x=1;*y=0;,return a;,if(a!=0)&(b!=0),x0=0;x1=1;r0=a;,y0=1;r1=b;,r2=r0%r1;y1=0-r0/r1;,x2=1;y2=y1;,扩展欧几里德算法,-,无递归实现,(,续,),while(r1%r2)!=0),r0=r1;r1=r2;,q=r0/r1;,x2=x0-x1*q;y2=y0-y1*q;,x0=x1;x1=x2;y0=y1;y1=y2;r2=r0%r1;,*x=x2;*y=y2;,return r2;,mx,+,ny,=,c,的整数解算法,设,d,=gcd(,m,n,),，记,m,=ad,，,n,=,bd,求特解：求整系数方程,mx,+,ny=d,的一个整数解,x,0,，,y,0,，,求一般解：,若,d,不是,c,的因数，则整系数方程,mx,+,ny,=,c,无整数解；,若,d,是,c,的因数，记,c=gd,，,则整系数方程,mx,+,ny,=,c,一般解为,：,x=gx,0,+bt,y=,g,y,0,-at,t,为任何整数,举例,求下列整系数方程的整数解：,答案：略,3,、求解模线性方程,1,）,模和同余,模和同余：,设,a,、,b,和,m,均为整数，且,m0,。如果,a,和,b,被,m,除所得的余数相同，那么称,a,和,b,关于,模,m,是,同余的，记作,几个等价定义：,b-a,能被,m,整除，记,m|a-b,a,和,b,关于,模,m,是,同余的,2,）同余性质,4,、设 ，,那么,1,、,2,、,3,、,(1),(2),(3),5,、费马小定理：设,a,，,p,为正整数，且,p,为素数，,(,p,a,)=1,，那么,剩余类与简化剩余系,剩余类：对于整数,a,及模,m,，则集合,A,=,x,|,x,a,(mod,m,),称为模,m,关于,a,的一个剩余类。,完全剩余系：,0,，,1,，,2,，,，,m-1,是一个特殊的集合，元素个数,m,，其中任何两个数都不同余，称为完全剩余系。,任何,m,个元素的集合,X,，如果其中任何两个数都不同余，那么,X,也是一个完全剩余系。,既约剩余系：设,m,为正整数，在与,m,既约的所有剩余类中，每一个类中取一个数，构成一个集合,X,，则,X,称为模,m,的一个简化剩余系。,举例,例,1,：若,p,是素数，则,1,，,2,，,3,，,，,p,-1,是模,p,的一个既约剩余系。,例,2,：,1,，,5,，,7,，,11,是模,12,的一个既约剩余系。,问题：与正整数,m,既约且小于等于,m,的自然数全体之积,Y,被,m,除后余数是几？,举例：,m=7,，,Y=1,*,2*3*4*5*6(mod 7),-1,(mod 7),，正余数为,6,；,m=13,，,Y=1,*,2*3*4*5*12(mod 13),(-1,)(13-1)/2,(mod 13),，正余数为,1,；,m=21,，,Y=,1,*,2,*,4,*,5,*8*,10,*,11,*13*,16,*,17,*,19,*,20,Y(mod 21)1 (mod 21),2,）模线性方程,相当于求,根据前面求 的步骤：,（,1,）求 ，使,否则，有,d,个解,（,4,）的所有解可写为：,（,3,）由 ，改写得：,于是 的一个解为：,（,2,）若,d b,，则,无解；,方程与同余式求解举例,（,2,）求,（,3,）求,例：（,1,）求,4,、求,mod m,的逆元素算法,对整数,a,，满足,ax,1(mod,m,),的解,x,称为,a,关于模,m,的逆元素,。,是前面模线性方程的特例。,结论：对整数,a,，,m,（,m,0,）,ax,1(mod,m,),有解，当且仅当，,gcd(,a,，,m,)=1,也可用直接用扩展欧几里得算法进行求解。,求 的算法,举例,求解：,（,1,）,（,2,）,（,3,）,（,4,）,求,mod m,的逆元素的无递归程序：,long mod_reverse(long a,long m),long y=0,x=1,r=a%m,q,t,mm=m;/,初始化,if(r0)r=r+m;,while(m%r)!=0),a=m;m=r;,q=a/m;r=a%m;,t=x;x=y-x*q;y=t;,if(r!=1)return 0;,if(x0)x=x+mm;,return x;,5,、模线性方程组与中国剩余定理,“,韩信点兵,”,问题,：,有兵一列，三三数之余二，五五数之余三，七七数之余二，问兵几何？,可写成数学表示形式，求,x,求解模线性方程组,中国剩余定理,求解步骤,例：解同余方程组,中国剩余定理,程序实现,long ChinaRemainder(int m0,int b),long d,x,y,n,m=1,a=0;,int i;,for(i=1;i=n;i+)m=m*m0i;,for(i=1;i=n;i+),MM=m/m0i;,extend_gcd(MM,m0i,/,或,x=mod_reverse(MM,m0i);,a=(a+MM*x*bi)%m;,return a;,6,、模幂运算与素数测试,模幂运算就是在一个模下,计算一个幂的值，即计算,(,a,，,r,和,m,是正整数,),素数测试就是指，在尽可能短的时间内，尽可能精确地判断一个整数是否是素数。通过,费马小定理来判定,一个,整数的素性,，因此求模幂是重要任务。,1,）模幂运算,（,1,）模幂运算,1,累次计算法,：,d,a,r,mod m,(,(a mod m)*a)mod m)*a)mod m,*a)mod m,算法,long modular_power1(long a,long r,long m),long d=1,k;,a=a%m;for(k=0,；,k0),if(r%2)=1)d=(d*t)%m,；,r=r/2;,t=t*t%m;,return d;,练习,计算,2,）素数测试,费马小定理：设,a,，,p,为正整数，且,p,为素数，,(,p,a,)=1,，那么,有例外，如,2,340,1,（,mod 341,），但,341,是合数。,素数测试：设,a,、,n,为正整数,（,1,）若 ，则,n,一定为合数,（,2,）若 ，则几乎可以肯定地确认,n,为素数，因出错概率很小,Miller-Rabin,素数测试算法框架,输入：,n,与,a,（,a,在,2,，,，,n,-1,这些数中随机取值）,输出：,true,或,falseS1.,设,(b,k,b,k-1,b,1,b,0,),为,n-1,的二进制表示,S2.d=1,S3.For i=k downto 0 do,x=d,d=(d*d)mod n,if(d=1)and(x,1)and(x,n-1)then,return true,if(b,i,=1)then d=(d*a)(mod n),End For,S4.if(d,1)then return true,S5.return false,3,）欧拉定理,设,a,和,m,是整数，（,m,0,）。记,(,m,),是,1,到,m,的整数中与,m,互素的整数的个数，则,a,(m),1(mod,m,),。,费马小定理是欧拉定理的特例,4,）公钥密码与,RSA,公开密钥算法是在,1976,年由美国斯坦福大学的迪菲（,Diffie,）和赫尔曼,(Hellman),提出,目前最流行的,RSA,是,1977,年由,MIT,教授,Rivest,Shamir,和,Adleman,三人共同开发。,密钥的产生,选择两个大素数，,p,和,q,，计算出,n=qp,，,n,称为,RSA,算法的模数。,n,公开，,p,、,q,必须保密。,n,的长度大于,1024,位,计算,n,的欧拉数,(n)=(p-1)(q-1),。,随机选择加密密钥,e,，从,0,(n)-1,中选择一个与,(n),互质的数,e,，,e,公开,计算解密密钥,d,满足de1(mod,(n),。其中,n,和,d,也要互质。数,e,和,n,做公钥，,d,做私钥。,两个素数,p,和,q,不再需要，应该丢弃，不让任何人知道。,加密与解密,加密信息,m,（二进制表示）：首先把,m,分成等长数据块,m,1,m,2,.,m,i,，块长,s,，其中,2,s,n;,do,n/=5;,count+=n;,while(n);,coutcount1,，那么不能表示成,Ax+By,形式的邮资的个数有无穷多，如以下数都不是,Ax+By,形式：,1,、,1+,A,B,、,1+2,A,B,、,、,1+,n,A,B,、,如,d=gcd(A,B)=1,，结果如何？,在,0,到,AB,-1,内有 个整数,m,可以写成,m=As+Bt,的形式，,s,，,t,是非负整数,。,分析,以下设,d=gcd(,A,B,)=1,。,结论：值至少为,AB,的邮资都是可以用这两种邮票支付的。不能支付的不超过,AB,-1,个，而且可以用一个公式表示。,需证明以下几点：,不妨设,A,B,。对整数,n,，,0,n,B,，有整数,x,、,y,，使,n,=,Ax,+,By,，,且满足,0=,AB,时，任何,m,均可表示成,Ax+By,的形式，,x,=0,，,y,=0,。,不能表示成,Ax,+,By,形式的数的个数为,参考程序：易，略,4 Josephus,问题,问题描述：,Josephus,问题：一群小孩围成一圈，任意给定一个数,m,，从第一个小孩开始，顺时针方向数，每数到第,m,个小孩时，该小孩便离开。小孩不断离开，圈子不断缩小。最后剩下的一个小孩是胜利者。究竟胜利者是第几个小孩呢？,输入：,有若干组测试数据。每一行有一个整数,num,，,m,，分别代表小孩个数和每隔多少小孩数数。,num,，,m,10000,。,输出：,对每一组测试数据，单行输出获胜的小孩的编号。,输入与输出样例,输入样例：,10 8,10 2,输出样例：,1,5,分析,方法一：模拟法,实际模拟数小孩出列的过程。用一个数组表示小孩围成圈。对每个小孩赋以一个序号值作为小孩的标志。,采用,“,加,1,求模,”,，当数到数组尾的时候，下一个数组下标值可以算得为,0,，从而回到数组首以继续整个过程。,设：,Max=10000;,小孩最大个数,num,为小孩个数，,aMax;,小孩数组,每次数,m,个小孩，便让该小孩离开；下标加,1,求模，使下标到达尾部后能返回到数组头。,参考代码一：见下页,#include,using namespace std;,int main(),const int Max=10000;,int num,m,aMax;,while(cinnumm),for(int i=0;inum;i+),ai=i+1;/,小孩编号,int k=1;,/,标识处理第,k,个小孩的离开,int i=-1;,/,初值while(1)/,圈中数,m,个小孩,for(int j=0;jm;),i=(i+1)%num;,if(ai!=0)j+;,if(k=num)break;,/,该小孩是最后一个吗？,/,是，则为胜利者,ai=0;/,标识该小孩离开,k+;/,准备处理圈中的,/,下一个小孩,coutendl;,cout ainumm),r=0;,for(int k=1;k=num;+k)r=(r+m)%k;,coutr+1endl;,return 0;,5,负数进制转换,问题描述（大意）：,设计一个程序，读入一个十进制数和一个负进制的基数，并将此十进制数转换成为此负进制下的数：,-R-2,-3,-4,.-20,例如，十进制数,-15,，相当于,-2,进制数,110001,：因,110001=1*(-2),5,+1*(-2),4,+0*(-2),3,+0*(-2),2,+0*(-2),1,+1*(-2),0,输入,输入的每行有两个数据,N,、,-,R,。,N,是十进制数，（,-32768,N,32767,），,-,R,是负进制数的基数。,输出,相对于每组输入，应输出此负进制数及其基数，若此基数超过,10,，则参照十六进制的方式处理。,输入与输出样例,输入样例,输出样例,30000,2,-20000,2,28800,16,-25000,16,30000=11011010101110000(base-2),-20000=1111011000100000(base-2),28800=19180(base-16),-25000=7FB8(base-16),分析,采用与正数进制的转换相类似的方法。,对负数进制，每次取的余数保证在,0R-1,之间，就可以直接输出。,例如,-R=-16,，则余数应该在,015,。所以用模“,%”,运算符的时候必须注意检查是不是在该范围（可能在,-R+10,），否则就调整。,调整的方法是：,if,（余数,mbase),k=m;memset(a,0,sizeof(a);,i=0;,while(true),r=m%base;,m=m/base;,if(r=0;i-)coutai;,cout(base base;,cout)endl;,return 0;,任意范围基数转换表,char map(int temp),if(temp=9),return 0+temp;,else,return A+(temp-10);,6,数塔问题,问题描述,对任意正整数,n,，求由,n,层,n,构成的数的个位数。,输入,输入文件的第,1,行是整数,T,，（,0T=50,），接下来的,T,行每行有一个整,数,n,，（,0n=10,10,）。,输出,对输入中的每个,n,，对应于输出中的一行，内容是由,n,层,n,构成的数的个位数。,输入与输出样例,输入样例,输出样例,3,12,42,356,6,5,分析,设,n,的个位数为,a,，即，或,n,=10,q,+,a,，再设 的个位数为,A,，指数为,m,，那么由 得,A,=,。,分情况对,a,进行讨论：,a=09,如果,a,=0,，,1,，,5,或,6,，那么,A,仍分别为,0,，,1,，,5,或,6,。,如果,a,=2,，那么,2,1,2,，,2,2,4,，,2,3,8,，,2,4,6,，,2,5,2(mod 10),2,的幂,2,t,的个位数循环出现，周期是,4,。,如设指数,t,=4,k,+,r,，,r,=1,，,2,，,3,，,4,，那么,2,t,的个位数仅与,r,有关。,分析,(,a,=2),：只需计算,m,被,4,除得的余数。因,n,为偶数，所以,m,也为偶数。如果,n,本身是,2,，那么,A,=4,；在其他情况下，,m,的指数是也是偶数,2,p,，此时,m,能被,4,除尽，即,r,=4,。此时,A,=6,。,根据,2.,类似的讨论，以下简单地讨论：,如果,a,=3,，,n,=10,q,+3,。,再设,q,=2,p,+,s,。,周期是,4,。,设,m,的指数,t,=4,k,+,r,，,r,=1,，,2,，,3,，,4,。,若,s,=0,，则,m,被,4,除的余数是,3,，此时,A,=7,。,若,s,=1,，则,m,被,4,除的余数仍是,1,，此时,A,=3,。,如果,a,=4,，,周期是,2,。,m,是一个偶数，此时,A,=6,。,分析,如果,a,=7,，,n,=10,q,+7,，,周期是,4,。,若,q,为奇数，则,n,被,4,除的余数是,1,，,A,=7,。,若,q,为偶数，则,n,被,4,除的余数是,3,，,A,=3,。,如果,a,=8,，,n,=10,q,+8,，,周期是,4,。幂,m,的底是,n,，为偶数，其指数也是偶数。在这种情况下，,A,=6,。,如果,a,=9,，,周期是,2,。,A,=9,7,幸运数,问题描述,中国人认为,8,是一个幸运数字。鲍勃也认为是这样，而且他有他自己的幸运数,L,。现在他要构造他的幸运数，该数是仅由数字,8,组成且是,L,的倍数中最小的那个正整数。,输入,输入有多组测试数据，每一组仅由一行上的一个正整数,L,构成，,(1=L3),因子。,Case 1,：,L,有因子,16,，那么无法找到这个幸运数,H,Case 2,：,L,有因子,5,，那么无法找到这个幸运数,H,Case 3,：,L,有因子,2,t,(t4),。设,L,=2,t,m,，,m,为无,有因子,5,的奇数。,Case 3,进一步讨论,表明 是,m,的倍数,所以有,这里，,(9,m,，,10)=1,。,由欧拉定理，可得,由 得,由于,k,是所求数的最小长度，因此必有,Case 3,算法,计算,9,m,，并求欧拉函数,值,(9,m,),，记,M,=,(9,m,),。,求,M,的素因子分解，在,M,的因子中从较小的因子开始作为,k,，尝试验证 。,判断：如果成立，那么就找到最小的,k,，终止查找。,8,哥德巴赫猜想,问题描述,哥德巴赫是一位德国的业余数学家。,1742,年，他写信给当时的数学家欧拉，信中提出如下猜想：,每个大于,4,的偶数都可以写成两个奇素数之和。,例如：,8=3+5,，,3,和,5,都是奇素数，,20=3+17=7+13,42=5+37=11+31=13+29=19+23.,直到现在，仍未证明该猜想是否是真的。不管怎样，你的任务是对于,100,万以内的偶数验证哥德巴赫猜想。,输入,有多组测试数据，每组测试数据由一个偶数,n,构成（,6,n,1000000当输入是,0,时表示输入结束。,输出,对每种测试数据，输出形如,n,=,a,+,b,的表达式，其中,a,和,b,是奇素数，加号应该用空格隔开，如下面的输出样例。如果有多对奇素数满足，仅取差,b,a,最大的一组。如果没有这样的素数对，那么输出,“,Goldbachs conjecture is wrong.,”,输入与输出样例,输入样例,8,20,42,0,输出样例,8=3+5,20=3+17,42=5+37,分析,对于偶数,n,，可以取不大于,n,/2,的奇数,p,，记,q,=,n,-,p,，即写,n,=,p,+,q,。,本题测试数据较弱，可用常规的判定素数的,埃拉托色尼筛法,做，直接判定,p,和,q,是否为素数。,为求满足差,b,a,最大的一组，只要从,3,开始到不大于,n,/2,的奇数依次作为,p,。当,n,1000000,时，采用常规方法，有超时的可能。,也可尝试用,Miller-Rabin,素数测试,该算法并不能保证待测整数一定是素数，但对素数测试的正确性随着测试次数的增加而增加。以下程序中采用了二次测试。,练习：四个素数之和问题,欧拉证明素数有无穷多个。但每个整数能表示成四个素数之和吗？我也不知道这一答案，希望你能帮助我。我希望你能高效率地解决这一问题。,输入：每行输入一个整数,N,（,N=10000000,），它是你需要把它表示成四个素数之和的数。输入直到文件结束为止。,输出：对于每个输入行都有一个输出行，每行包含符合要求的四个素数。如果该数不能表示为四个素数之和，那么输出一行“,Impossible.”,。也可能有多组解，任何合理的解都将被接受。,输入与输出举例,输入样例,24,36,46,输出样例,3 11 2 7,3 7 13 13,11 11 17 7,9 for,循环语句执行次数,问题描述,有一个,C,语言型的,for,循环语句：,for(j=0;(j-b)%p!=0;j+=a),statement;,即该循环中循环变量,j,的初值为,0,，只要,(j-b)%p,不等于,0,就加,a,值后进行循环。我们要知道语句“,statement,”执行了多少次。,输入,：,输入有多组测试数据。每组数据由一行上的三个整数,a,b,p,构成，数据之间空一格。这里假定,a,b,和,p,满足,0,a,b p,，,1,p,10,9,。,输出,对每组测试数据，输出一个结果。如果,for,循环无法终止，那么输出“,Infinite,”，否则输出,for,循环执行的次数,x,，即要求,x,是满足,0,x p,的最小整数。,输入样例,13 2 245,7 2 181,13 2 74,3 334 216,输出样例,19,52,40,Infinite,网上练习,青蛙的约会：,poj1061,时钟：,Pku1166,Latex,中作有向线段问题：,SHU318,二次剩余,:,SHU 201,