文档介绍：第8章 数论算法及计算几何算法
现在学****的是第1页，共32页
教学目标
理解求最大公约数的算法
掌握欧几里德公式的推广
掌握求解同余方程的算法
掌握运用中国剩余定理解决实际问题
理解线段相交的概念
掌握线段是否相交的判定算法
理解凸包的概念及穷举搜索的解决方法
掌握凸包问题及最接近点对问题的分治法
现在学****的是第2页，共32页
定义1 设a，b是整数，b≠0，如果存在整数c，使得a=bc成立．则称a被b整除，a是b的倍数，b是a的约数(因数或除数)，可记为b|a；如果不存在整数c使得a＝bc成立，则称a不被b整除，记为ba。
定理1(带余数除法) 设a与b是两个整数，b≠0，则存在唯一的两个整数q和r，使得a=bq+r，0≤r<|b|。（证明略）
定义2 在定理1的表达式a=bq+r中，称q是a被b除的商，r是a被b除的余数。
最大公约数是指两个或两个以上整数的公共约数中最大者。
现在学****的是第3页，共32页
欧几里德定理
任意给定两个整数a,b，不妨假设a≥b。它们的最大公约数用gcd(a，b)表示，则gcd(a，b)=gcd(b，a mod b) ，其中a mod b表示a被b除所得的余数
欧几里德递归定义式
现在学****的是第4页，共32页
应用举例（求100和210最大公约数）
欧几里德递归公式的推广
来解决“已知a, b求解一组x，y使得ax+by=gcd(a, b) ”问题
令gcd(a, b)=d，则ax+by=d；gcd(b,a mod b)=d (8-1)
（1）当b=0时，则gcd(a,b)=a；ax+by=a，即ax=a，则x=1，y取任意实数。简单起见，算法取y=0；
（2）当b≠0时，令a'=b，b'=a mod b，则gcd(a', b')=d，a'x'+b'y'=d。
由于b' =a mod b = ，则a'x'+b'y'=bx'+( )y'=ay' +b(x' -y')=d (8-2)
让式(8-1)和式(8-2)对应项相等，则x=y'，y= x' -y'。
现在学****的是第5页，共32页
Stein算法
基于的两条结论
（1）gcd(a，0)=a。
（2）gcd(ka，kb)=k gcd(a，b)
算法步骤
步骤1：初始时，令c=1；
步骤2：如果a=0，c=b*c；如果b=0，c=a*c；算法结束。
步骤3：令a1=a，b1=b；
步骤4：a和b奇偶性的判断。
现在学****的是第6页，共32页
如果a和b都是偶数，则a=a/2，b=b/2，c=2*c；
如果a是偶数，b不是偶数，则a=a/2；
如果b是偶数，a不是偶数，则b=b/2；
如果a和b都不是偶数，则a =|a1 –b1|，b=min(a1,b1)；
转步骤2。
应用举例
求15和9的最大公约数
现在学****的是第7页，共32页
同余式
设a、b和m为整数，其中m＞0。若a和b被m除得的余数相同，则称a和b对模m同余。记为 或
同余式的简单性质
（1）若a b(m)，则m|(b-a)。反过来，若m|(b-a)，则a b(m)；
（2）如果a=km+b(k为整数)，则a b(m)；
（3）每个整数恰与0,1,…，m-1这m个整数中的某一个对模m同余；
（4）同余关系是一种等价关系：
反身性 a a(m)；
对称性a b(m)，则b a(m)，反之亦然；
传递性a b(m)，b c(m)，则a c(m)。
（5）如果a b(m)，x y(m)，则
① a x (b y)(m);
② 特别地 。
现在学****的是第8页，共32页
例1：使2n+1能被3整除的一切自然数n
例2：求2999最后两位数码
同余方程
设 是整系数多项式，m是正整数，称f(x) 0(mod m) (8-4)
是关于未知数x的模m的同余方程，简称为模m的同余方程。若 则称式(8-4)为n次同余方程
同余方程的解
设x0是整数，当x＝x0时式(8-4)成立，则称x0是同余方程(8-4)的解。凡对于模m同余的解，被视为同一个解
现在学****的是第9页