1、第八章 数论算法及计算几何算法教学目标 理解求最大公约数的算法 掌握欧几里德公式的推广 掌握求解同余方程的算法 掌握运用中国剩余定理解决实际问题 理解线段相交的概念 掌握线段是否相交的判定算法 理解凸包的概念及穷举搜索的解决方法 掌握凸包问题及最接近点对问题的分治法8.1最大公约数 定义 1 设 a， b是整数， b0，如果存在整数 c，使得a=bc成立则称 a被 b整除， a是 b的倍数， b是 a的约数 (因数或除数 )，可记为 b|a；如果不存在整数 c使得 a bc成立，则称 a不被 b整除，记为 ba。 定理 1(带余数除法 ) 设 a与 b是两个整数， b0，则存在唯一的两个整数
2、q和 r，使得 a=bq+r， 0r|b|。（证明略） 定义 2 在定理 1的表达式 a=bq+r中，称 q是 a被 b除的商， r是 a被 b除的余数。 最大公约数是指两个或两个以上整数的公共约数中最大者。8.1.1欧几里德算法 欧几里德定理 任意给定两个整数 a,b，不妨假设 ab。它们的最大公约数用 gcd(a， b)表示，则 gcd(a， b)=gcd(b， a mod b) ，其中 a mod b表示 a被 b除所得的余数 欧几里德递归定义式 应用举例（求 100和 210最大公约数） 欧几里德递归公式的推广 来解决 “已知 a, b求解一组 x， y使得 ax+by=gcd(a,
3、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）当 b0时，令 a=b， b=a mod b，则 gcd(a, b)=d，ax+by=d。 由于 b =a mod b = ，则 ax+by=bx+( )y=ay +b(x -y)=d (8-2) 让式 (8-1)和式 (8-2)对应项相等，则 x=y， y= x -y。 8.1.2 Stein算法 基于的两条结论 （ 1） gcd(a， 0)=
4、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奇偶性的判断。 如果 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的最大公约数8.2同余方程 同余式 设 a、 b和 m为
5、整数，其中 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); 特别地 。
6、例 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同余的解，被视为同一个解 一次同余方程 设 a， b为整数，且，则称同余方程 ax b(mod m) (8-5)为一次同余方程。 定义 7 设 a1,a2,an 是非零整数， b是整数，称关于未知数 x1,x2, xn的方程a1x1+a2x2+ anxn=b是 n元一次不定方程。 定理 3 一次同余方程有解的充要条件是gcd(a,m)|b。若有解，则恰有 d=gcd(a， m)个解。 证明（见板书） 一次同余方程的求解步骤
