算法竞赛专题解析（20）：数论

本系列文章将于2021年整理出版。前驱教材：《算法竞赛入门到进阶》 清华大学出版社 网购：京东 当当   作者签名书：点我 公众号同步：算法专辑    暑假福利：胡说三国 有建议请加QQ 群：567554289

   最大公约数[1]和最小公倍数（Least Common Multiple）是竞赛中频繁出现的考点。

   整数a和b的最大公因数是指能同时整除a和b的最大整数，记为gcd(a, b)。    例如：gcd(15, 81) = 3，gcd(0, 44) = 44，gcd(0, 0) = 0，gcd(-6, -15) = 3，gcd(-17，289) = 17。    注意：由于-a的因子和a的因子相同，因此gcd(a, b) = gcd(|a|, |b|)。编码时只需要关注正整数的最大公因数。

  （1）gcd(a,b) = gcd(a, a+b) = gcd(a, ka+b)   （2）gcd(ka, kb) = k·gcd(a, b)   （3）定义多个整数的最大公约数：gcd(a, b, c) = gcd(gcd(a, b), c)   （4）若gcd(a, b) = d，则gcd(a/d, b/d) = 1，即a/d与b/d互素。这个定理很重要。   （5）gcd(a+cb, b) = gcd(a, b)

  编程时可以直接用c++函数std::__gcd(a, b)。注意：参数a和b都应该是正整数，否则可能会返回负数。下面介绍三种算法。

  用辗转相除法求gcd，即gcd(a, b) = gcd(b, a mod b)。代码是：

  这是竞赛中最常用的编码，它极为高效，“拉梅定理”给出了复杂度分析。   拉梅定理：用欧几里得算法计算两个正整数的最大公因数，需要的除法次数不会超过两个整数中较小的哪个十进制数的位数的5倍。   推论：用欧几里得算法求gcd(a, b)，a > b，需要\(O((log_2a)^3)\)次位运算。   欧几里得算法的缺点是需要做除法取模运算，而高精度大数的除法比较耗时，此时可以用“更相减损术”[2]和stein算法，它们只用到了减法和移位操作。

  不过，在竞赛中不太可能直接使用“更相减损术”和stein算法求最大公约数。下面的介绍，只是为了帮助读者理解GCD的性质。

  计算基于这一性质：gcd(a, b) = gcd(b, a-b) = gcd(a, a-b)。

  计算步骤：用较大的数减较小的数，把所得的差与较小的数比较，然后继续做减法操作，直到减数和差相等为止。   编码也很简单：

  更相减损术虽然避免了欧几里得的取模计算，但是计算次数比欧几里得算法多很多，极端情况下需要计算\(O(max(a, b))\)次，例如a = 100，b = 1时，需计算100次。

  它是更相减损术的改进。求gcd(a, b)时，可以分为几个情况进行优化：   1）a、b都是偶数。gcd(a, b) = 2gcd(a/2, b/2)，计算减半。   2）a奇b偶（或a偶b奇）。根据这一原理：若k与y互为质数，有gcd(kx, y) = gcd(x, b)。k = 2时，有gcd(a, b) = gcd(a/2, b)，即偶数减半。   3）a、b都是奇数。gcd(a, b ) = gcd( (a+b)/2, (a-b)/2 )。   算法的结束条件仍然是gcd(a, a) = a。   除2操作用移位就可以了，所以Stein算法只用到加减法和移位。   关于高精度大数的GCD计算，读者可以用下面这一题练习，类似的题有hdu 5050。

SuperGCD 洛谷 P2152 题目描述：求2个正整数a，b的最大公约数，0 < a, b ≤ \(10^{10000}\)。

  不过，由于OJ都支持java，比赛的时候直接用java函数处理大数是最简单的：

  a和b的最小公倍数lcm(a, b)，可以从算术基本定理推理得到。   算术基本定理（唯一分解定理）：任何大于1的正整数n都可以唯一分解为有限个素数的乘积：\(n = p_1^{c_1}·p_2^{c_2}...·p_m^{c_m}\)，其中\(c_i\)都是正整数，\(p_i\)都是素数且从小到大。   设：\(a = p_1^{c_1}·p_2^{c_2}...·p_m^{c_m}\)，\(b = p_1^{f_1}·p_2^{f_2}...·p_m^{f_m}\)   那么：     \(gcd(a, b) = p_1^{min\{c_1,f_1\}}·p_2^{min\{c2,f2\}}...·p_m^{min\{cm,fm\}}\)，     \(lcm(a, b) = p_1^{max\{c_1,f_1\}}·p_2^{max\{c2,f2\}}...·p_m^{max\{cm,fm\}}\)   推出：     \(gcd(a, b)*lcm(a,b)=a*b\)，   即:     \(lcm(a,b)= a*b/gcd(a, b) = a/gcd(a, b)*b\)。   注意先做除法再做乘法，如果先做乘法可能会溢出[3]。

  （1）hdu 5019   题目描述：给出整数x、y、k，求x、y的第k大公约数。   题解：先求最大公因数d = gcd(x, y)，由于其他公因子都是d的因子，那么从1到\(\sqrt{d}\)（注意不需要到d）逐个检查是否能整除d，即可找到所有公因子。

  （2）hdu 2503   题目描述：给出2个分数a/b和c/d，求a/b + c/d，要求是最简形式。   题解：a/b + c/d = (ad + bc) / bd，分子和分母除以两者的最大公约数。

   （3）hdu 2504   题目描述：已知a和b，求满足gcd(a,c) = b的最小的c。   题解：暴力搜b到a*b内符合条件的c。

  （4）hdu 4497   题目描述：给定两个正整数G、L，问满足gcd(x, y, z) = G和lcm(x, y, z) = L的(x, y, z)有多少个？注意，(1, 2, 3)和(1, 3, 2)是不同的。   题解。此题利用了GCD的几个性质：   1）若gcd(a, b) = d，则gcd(a/d, b/d) = 1，即a/d与b/d互素；   2）\(gcd(a, b) = p_1^{min\{c_1,f_1\}}·p_2^{min\{c2,f2\}}...·p_m^{min\{cm,fm\}}\)   3）\(lcm(a, b) = p_1^{max\{c_1,f_1\}}·p_2^{max\{c2,f2\}}...·p_m^{max\{cm,fm\}}\)   若L % G ≠ 0，显然无解。下面分析L % G = 0的情况。   把问题转化为：满足gcd(x/G, y/G, z/G) = 1和lcm（x/G，y/G，z/G）= L/G的(x/G, y/G, z/G)有多少个。下面用排列组合分析有多少种情况。   根据算术基本定理，把x/G、y/G、z/G写成：     x/G = \(p_1^{i_1}·p_2^{i_2}·p_3^{i_3}\)     y/G = \(p_1^{j_1}·p_2^{j_2}·p_3^{j_3}\)     z/G = \(p_1^{k_1}·p_2^{k_2}·p_3^{k_3}\)   式子要满足x/G、y/G、z/G互素的条件。以{\(i_1, j_1, k_1\)}为例，其中至少有1个应该等于0。   另外，把L/G写成：     L/G = \(p_1^{t_1}·p_2^{t_2}·p_3^{t_3}\)   式子要满足lcm（x/G，y/G，z/G）= L/G。以{\(i_1, j_1, k_1\)}为例，允许的情况是：   1）{0, 0, \(t_1\)}，有三种排列；   2）{0, \(t_1\), \(t_1\)}，有三种排列；   3）{0, \(t_1\), 1 ~ \(t_1\)-1}，有(\(t_1\)-1)*6种排列；   加起来一共有 \(t_1\)*6 种排列。   最后问题转化为求\(t_1\)、\(t_2\)、\(t_3\)，即分解 L/G 的质因子。

  GCD的题目一般和其他知识点结合出题。   hdu 2104，互素判定   hdu 3092，GCD+完全背包   hdu 5970，GCD+循环节   hdu 5584，LCM问题   洛谷 P2568 ，GCD + 莫比乌斯反演   洛谷 P2398，GCD求和   洛谷 P1890，询问区间内的GCD   poj 1722，GCD思维题   poj 2685，GCD+快速幂   poj 3101，大数GCD   poj 2429，GCD + Rabin-Miller测试

最大公约数有多种英文表述：Greatest Common Divisor(GCD)、Greatest Common Denominator、Greatest Common Factor(GCF)、Highest Common Factor (HCF)。 ↩︎

欧几里得《几何原本》是公元前三世纪的著作，中国《九章算术》成于公元一世纪，流行本是三世纪刘徽的注本，都非常古老。“更相减损术”在《九章算术》卷一的“约分”这一节：“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。”本文给出的代码省去了a、b为偶数的情况，即“可半者半之”。 ↩︎

参考：《算法竞赛入门经典（第2版）》，刘汝佳，清华大学出版社，312页。 ↩︎