Greatest Common Divisor

# Math 本小节总结一些与数学（尤其是数论部分）有关的基础，主要总结了《挑战程序设计竞赛》第二章。 ### 最大公约数(GCD, Greatest Common Divisor) 常用的方法为辗转相除法，也称为欧几里得算法。不妨设函数`gcd(a, b)`是自然是`a`, `b`的最大公约数，不妨设`a > b`, 则有 a=b×p+qa = b \times p + qa=b×p+q, 那么对于`gcd(b, q)`则是`b`和`q`的最大公约数，也就是说`gcd(b, q)`既能整除`b`, 又能整除`a`(因为 a=b×p+qa = b \times p + qa=b×p+q, `p`是整数)，如此反复最后得到`gcd(a, b) = gcd(c, 0)`, 第二个数为0时直接返回`c`. 如果最开始`a < b`, 那么`gcd(b, a % b) = gcd(b, a) = gcd(a, b % a)`. 关于时间复杂度的证明：可以分`a > b/2`和`a < b/2`证明，对数级别的时间复杂度，过程略。 与最大公约数相关的还有最小公倍数(LCM, Lowest Common Multiple), 它们两者之间的关系为 lcm(a,b)×gcd(a,b)=∣ab∣ lcm(a, b) \times gcd(a, b) = |ab|lcm(a,b)×gcd(a,b)=∣ab∣. ### Java ~~~ public static long gcd(long a, long b) { return (b == 0) ? a : gcd(b, a % b); } ~~~ ### Problem 给定平面上两个坐标 P1=(x1, y1), P2=(x2,y2), 问线段 P1P2 上除 P1, P2以外还有几个整数坐标点？ #### Solution 问的是线段 P1P2, 故除 P1,P2以外的坐标需在 x1,x2,y1,y2范围之内，且不包含端点。在两端点不重合的前提下有： y−y1x−x1=y2−y1x2−x1\frac{y-y_1}{x-x_1}=\frac{y_2 - y_1}{x_2 - x_1}x−x1y−y1=x2−x1y2−y1那么若得知 M=gcd(x2−x1,y2−y1)M = gcd(x_2 - x_1, y_2 - y_1)M=gcd(x2−x1,y2−y1), 则有 x−x1x - x_1x−x1 必为 x2−x1/Mx_2 - x_1 / Mx2−x1/M 的整数倍大小，又因为 x1 a′x+b′y=1/Ma^\prime x+b^\prime y=1/Ma′x+b′y=1/M 如果 M 大于1，由于等式左边为整数，故等式不成立，所以要想题中等式有解，必有`gcd(a, b) = 1`. **扩展提：题中等式右边为1，假如为2又会怎样？** 提示：此时c=k⋅gcd(a,b),x′=k⋅x==>c % gcd(a,b)==0c = k \cdot gcd(a, b), x^\prime = k\cdot x ==> c\ \%\ gcd(a, b) == 0c=k⋅gcd(a,b),x′=k⋅x==>c % gcd(a,b)==0, c 为等式右边的正整数值。详细推导见 [How to find solutions of linear Diophantine ax + by = c?](http://math.stackexchange.com/questions/20717/how-to-find-solutions-of-linear-diophantine-ax-by-c)