1、第十二讲 数论第一节 最大公约数 首先，我们来回顾一下公约数和最大公约数的概念：如果 d是 a的约数并且也是 b的约数，则 d是 a与 b的公约数。例如,30的约数为 1， 2， 3， 5， 6， 0， 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)。 不
2、妨设 a=b，一种十分容易想到的算法是：枚举 1到 b的所有整数，在能同时整除 a和 b的数中取最大的。这个算法的时间复杂度为 O(min(a,b)，当 min(a,b)较大的时候程序要执行比较长的时间。在引出新算法之前，我们先来证明一个被称为 gcd(欧几里德 )的递归定理: gcd(a， b) gcd(b， a mod b)证明 : 我们只要证明出 gcd(a， b)与 gcd(b， a mod b)可互相整除，上式一定成立。设 dgcd(a， b)。将 a mod b 化成 a与 b的线性组合a mod b a a div b * b由于 d能整除 a和 b，因此 d一定能整除 a与 b
3、的线性组合，即 d能整除 (a mod b)。 又因为 d能整除 b和 (a mod b)，显然 d( gcd(a， b)能整除gcd(b， a mod b)。同理可证： gcd(b， a mod b)能整除 gcd(a， b)下述算法是一个直接基于 gcd定理之上的递归程序。该函数输入非负整数 a、 b，返回 a和 b的最大公约数。 function gcd(a， b:longint):longint;beginif b=0 thengcd:=aelsegcd:=gcd(b， a mod b)end;由于递归边界 gcd(a， 0) a正确且递归调用过程中第二个值参严格递减， 所以算法不可能
4、无限递归下去，在运行终止时总能求出正确的答案。例如 gcd(30， 21)的计算过程gcd(30， 21)=gcd(21， 9)=gcd(9， 3)=gcd(3，0)=3在这个计算过程中三次递归调用了 gcd。此算法的时间复杂度为 O(log(Max(a,b)。同理求这两个数的最小公倍数 LCM ( a , b ),直接利用公式：LCM ( a , b ) * GCD( a , b ) = a * b即可。 生活中许多有趣的问题，可以运用gcd定理来解答。例 12_1 狼找兔子 一座山周围有 n个洞，逆时针编号为 0， 1，2， .n-1。而一只狼从 0号洞开始，逆时针方向计数，每遇到 m个洞就进洞找兔子。例如 n=5， m=3，狼经过的洞依次为 0， 3， 1， 4， 2， 0。输入 n、 m。试问兔子有没有幸免的机会 ?如果有，该藏在哪儿 ? 分析： 不妨让兔子躲在一号洞。因为若狼能从 0号洞到达 1号洞，则它必能从 1号洞到达 2， .， n-1号洞，兔子难逃厄运。反过来说，若有安全洞，则 1号洞就是其中的一个。
