信息学冬令营讲座-数论

1、信息学冬令营讲座数论数论是研究数的性质的学科，是一门古老而充满现代魅力的数学学科。 数论基本上可分为初等数论、 解析数论、 代数数论等几个较大的分支。 在古代， 我国对数论的研究曾有过有辉煌的成就如孙子定理（国外文献一般称为中国剩余定理） 、商高定理 (勾股数 )、圆周率的计算等等。在现代，,我国一些著名的数学家，如华罗庚、王元、陈景润、潘承洞、丁夏畦等都在数论领域做出了一些举世公认的重要成果。过去，人们把数论归类为纯粹数学，但现在在许多领域，数论的原理和定理都得到了广泛的应用。例如计算机的计算模型、硬件体系结构和软件的设计与实现、代数编码、计算机通信安全与密码学等方面 , 都有着数论知识的广

2、泛应用。近年来发展起来的一门新兴学科“算法数论”就是用计算机算法来研究和深化数论的理论。 一个高层次的计算机专业人员， 应该掌握数论的一些基础知识。1求解二元一次不定方程我们的任务是解二元一次不定方程ax+by=c其中 a,b,c都是整数，所求的解(x,y)也是整数。方程如果有解，则解不是唯一确定的，所以我们称为不定方程。二元一次不定方程是一类重要的方程，应用很广。关于方程的可解性，有下面的两个重要的结论：（1）设 gcd(a,b)表示整数a,b 的最大公约数。 方程有解的充分必要条件是gcd(a,b)|c。（记号“ x|y”表示x 能整除y，即存在整数k，使y=kx ）。（2）如果(x 0,

3、y0) 是方程的一组解，则对任何整数t,(x0+bt,y0-at)也都是方程的解。许多讲数论的书都对这两个结论做了严格的论证。下面我们讨论具体求解的方法。为了避免计算中对负数和0 的讨论，我们假定a0， b0，并且 a=b。假定方程有解，即系数满足：gcd(a,b)|c，这时， c =c/gcd(a,b)一定是个整数。我们先讨论下面的方程：ax+by=f其中 f=gcd(a,b)，右端项恰好是左边两系数的最大公因子。显然，如果(x 0,y0) 是方程的一组解，则(c x0,c y0) 也是方程的一组解，即a(c x0)+b(c y0)=(c f)=c。在方程中，取a=107,b=73,c=1，

4、显然满足gcd(107,73)=1，方程107x+73y=1有解。我们用类似于求最大公约数的辗转相除的方法求这个解。利用辗转相除，可以得到：107=73*1+34, (1)73=34*2+5, (2)34=5*6+4,(3)5=4*1+1,(4)4=1*4 。(5)为了消去(3)中的” 4”，令(3)*1-(4): 34=5*7-1(6)为了消去(2)中的” 5”，令(2)*7-(6): 73*7=34*15+1(7)为了消去(1)中的” 34”，令(1)*15-(7): 107*15=73*22-1,即： 107*(-15)+73*22=1,于是，的一组解为（-15 ， 22）。下面归纳一般

5、的算法：将 (1)-(5)写成一般的形式：si =t i *q i +r i ，qi =si /ti ， r i =si %ti ， si+1 =t i ， t i+1 =r i 。认真分析上面的规律，可以归纳出具体的求解方法。我们先用下面的表格列出相应的关系：在下表中，i为辗转计算的次数。qi=si/ti为相除得到的商。我们看到ri等于后面一列的ti。i01234(end)5si107733454ti73345410qi12614ri345410 xi0121315yi1q0=131922表 14-1关键算法是 xk， yk 的递推计算公式：x0=0， x1=1； xi+1=xi*qi+xi

6、-1，当 i1 时。y0=1， y1=q0 ； yi+1=yi*qi+yi-1，当 i1 时。当 tk 0 且 rk=sk%tk=0时， k 就是最后一轮计算，这时，xk=15， yk=22 就是所要的结果，但要加上适当的符号后，才能得到原方程的解(x,y) ：x=(-1)k-1 xk ， y=(-1) k yk。关于 xi、yi的递推公式的推导较烦琐，就不在这里介绍了。对于方程，用这种方法可以求得x=-15 ， y=22 。程序：#include void result_one(int a,int b,int c,int *x2,int *y2)/*函数 1：计算不定方程的一组解*/int

7、q200,x200,y200;int d1,d2,i,r,t,j,gcd;x0=0;y0=1;d1=a;d2=b;for(i=0;i200;i+)qi=d1/d2;r=d1%d2; d1=d2;d2=r;if(r=0)gcd=d1; break;if(i=0)x1=1; y1=q0;elsexi+1=qi*xi+xi-1;yi+1=qi*yi+yi-1;for(t=-1,j=1;j0),b(0),c:n);scanf(%d%d%d,&a,&b,&c);result_one(a,b,c,&x2,&y2);test1(a,b,c,x2,y2);printf(x=%d y=%d n,x2,y2);关

8、于算法，还要说明两点：（1）如果 a,b 中有一个小于0，例如 a0 ， y0-at0就可以得到全部正整数解。另外，这个程序还有可以进一步简化的余地，例如在函数result_one()中，几个数组都可以不要，因为算出qi后， qi-2及前面的元素都没用了，可以只用3 个变量 q1,q2,q3 。程序效率会更高一些，而且不会发生数组下标越界的错误。对于xi， yi也是这样。习题 ： 现有容量为M，N 升的两个罐子（依次记为A,B）没有任何刻度，要求从水池中量出K 升水放到另一个容器里。其中M,N,K 都是正整数。例如，对于M=7,N=3,K=1，可以这样操作，先用A罐量 M升水，再利用 B 罐从

9、 A 罐中量两次 N 升水， A 罐中剩余的就是所要的 1 升水。编程输出操作过程，或输出“不可能” 。2求解三元一次不定方程我们的任务是解二元一次不定方程ax+by+cz=d如果 a,b,c中有一个数绝对值为1，例如 a=1,z 则有 x=d-by-cx于是，解可以表为：xdbucvu z v其中， u, v为任何整数。在具体计算中，如果不存在a=1, 可取绝对值最小的一个系数，例如仍然是a，将方程表为xdbycza然后，设法降低d, b,c的值。例：求解方程6x+20y-15z=23x20 y 15z233 y2z2 y 3z 1646于是，应有整数u，满足：2 y3z16u将上式改写为：

10、yzz13u2于是，应有整数 v，满足：z12v即： z2v1,yz v3u3v3u1x3 y2z4u 10u5v 3更一般的算法请自己归纳。3佩尔方程问题：由键盘输入一个整数N(N109) ，求不超过N 的最大整数n, 使1222n2n是一个完全平方数。分析：由1222n2n(n1)(2n 1) ,61222n2( n 1)(2 n 1) 2n23n 1 ,n66于是，问题归结为：求整数m,使2 n23n1 6m2.即：（ 4n3)23y21,这是佩尔方程： x23y21满足： x3(mod4),y0 (mod4)的解。由佩尔方程的理论： x23y21的正整数解 (x k ,y k ) 应满

11、足：xkyk 3(23) k再利用： xk3 (mod4),yk0 (mod4)就可以确定所需要的解。对于一般的佩尔方程：x2-dy 2=1, 当 d0 且 d 是完全平方数时，解只有（1，0）或（ -1 ， 0）。下面假定 d0 且 d 不是完全平方数，设(x1,y1)是方程的最小解x 0, y0且使 xd y最小则全部正整数解可表为：xn1( x12d y1) n( x1d y1 )n yn12 d( x1d y1) n( x1d y1 )n 上述 2式可以合并为：xnd yn(x1d y1 )n由此，容易导出递推公式：xn 1x1 xndy1 ynyn 1x1 yny1xn4 Fibon

12、acci数列1995 年 NOI）已知整数 m,n 满足： (n 2-nm-m2 ) 2=1， (1)求 m2+n2 的最大值，其中m,n106 由键盘输入。分析：如果m=n，只能有m=n=1，因此可假定m n，不妨设mn。令 n=m+uk，由 (1) 可导出 (m2-muk-u k2) 2=1，再令 m=uk+uk-1 , 由(1) 可导出 (u k2-u k uk-1 -u k-1 2) 2=1，由此可得序列：n， m， uk，uk-1 ， u1， u0 . 切满足 u 1=u0=1, 以及uk=uk-1 +uk-2 , ，即 u k 为 Fibonacci数列。清代 “红顶商人 ”胡雪岩说： “做生意顶要紧的是眼光，看得到一省，就能做一省的生意；看得到天下，就能做天下的生意；看得到外国，就能做外国的生意。浅或高远；一个人的希望和梦想，决定了他的人生暗淡或辉煌。”可见，一个人的心胸和眼光，决定了他志向的短人生能有几回搏，有生不搏待何时！所有的机遇和成功，都在充满阳光，充满希望的大道之上！我们走过了黑夜，就迎来了黎明；走过了荆棘，就迎来了花丛；走过了坎坷，就走出了泥泞；走过了失败，就走向了成功！一个人只要心存希望，坚强坚韧，坚持不懈，勇往直前地去追寻，去探索