Math

本小节总结一些与数学(尤其是数论部分)有关的基础,主要总结了《挑战程序设计竞赛》第二章。

最大公约数(GCD, Greatest Common Divisor)

常用的方法为辗转相除法,也称为欧几里得算法。不妨设函数gcd(a, b)是自然是a, b的最大公约数,不妨设a > b, 则有 a = b \times p + q, 那么对于gcd(b, q)则是bq的最大公约数,也就是说gcd(b, q)既能整除b, 又能整除a(因为 a = b \times 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/2a < b/2证明,对数级别的时间复杂度,过程略。

与最大公约数相关的还有最小公倍数(LCM, Lowest Common Multiple), 它们两者之间的关系为 lcm(a, b) \times gcd(a, b) = |ab|.

Java

  1. public static long gcd(long a, long b) {
  2. return (b == 0) ? a : gcd(b, a % b);
  3. }

Problem

给定平面上两个坐标 P1=(x1, y1), P2=(x2,y2), 问线段 P1P2 上除 P1, P2以外还有几个整数坐标点?

Solution

问的是线段 P1P2, 故除 P1,P2以外的坐标需在 x1,x2,y1,y2范围之内,且不包含端点。在两端点不重合的前提下有:


\frac{y-y_1}{x-x_1}=\frac{y_2 - y_1}{x_2 - x_1}

那么若得知 M = gcd(x_2 - x_1, y_2 - y_1), 则有 x - x_1 必为 x_2 - x_1 / M 的整数倍大小,又因为 x_1 < x < x_2, 故最多有 M - 1个整数坐标点。

扩展欧几里得算法

求解整系数 xy 满足 d = gcd(a, b) = ax + by, 仿照欧几里得算法,应该要寻找 gcd(b, a \% b) = bx^\prime + (a \% b)y^\prime.

Java

  1. public class Solution {
  2. public static int gcd(int a, int b) {
  3. return b == 0 ? a : gcd(b, a % b);
  4. }
  5. public static int[] gcdExt(int a, int b) {
  6. if (b == 0) {
  7. return new int[] {a, 1, 0};
  8. } else {
  9. int[] vals = gcdExt(b, a % b);
  10. int d = vals[0];
  11. int x = vals[2];
  12. int y = vals[1];
  13. y -= (a / b) * x;
  14. return new int[] {d, x, y};
  15. }
  16. }
  17. public static void main(String[] args) {
  18. int a = 4, b = 11;
  19. int[] result = gcdExt(a, b);
  20. System.out.printf("d = %d, x = %d, y = %d.\n", result[0], result[1], result[2]);
  21. }
  22. }

Problem

求整数 xy 使得 ax+by=1.

Solution

不妨设gcd(a, b) = M, 那么有 M(a^\prime x+b^\prime y)=1 ==> a^\prime x+b^\prime y=1/M 如果 M 大于1,由于等式左边为整数,故等式不成立,所以要想题中等式有解,必有gcd(a, b) = 1.

扩展提:题中等式右边为1,假如为2又会怎样?

提示:此时c = k \cdot gcd(a, b), x^\prime = k\cdot x ==> c\ \%\ gcd(a, b) == 0, c 为等式右边的正整数值。详细推导见 How to find solutions of linear Diophantine ax + by = c?