Number Theory

Posted on Edited on In , , , , , Word count in article: 941 Reading time ≈ 3 mins.

补点数论

  • 模运算 - Modular Arithmetic
  • 最大公约数 - Greatest Common Divisor
  • 最小公倍数 - Least Common Multiple

除法 - Division

定义

对于整数 和 ， 且 ， 若存在整数 和 使得 ，其中 。
特别的有，当 时，则称 整除 ，其中称 为 的约数(factor or divisor)，记为 否则为

模运算 - Modular Arithmetic

定义

由除法定义

同余

有，若 或其等价形式 ，则称 同余 模 ，记为

一些性质

最大公约数 - Greatest Common Divisor

原理

  • 此处为欧几里得算法

设 ，有 设 则
可知 为整数，也即 ，所以 的公约数，也会是 的公约数
另外，若设 ，
可知等式左边为整数，所以 的公约数 也会是 也会是 的公约数
因此可得

观察 ， 可以发现，是不断减小的，由此我们得到了一个递归的算法

实现

1
2
3
4
int gcd(int a, int b) {
  // b = 0 时即在上一轮迭代中 a = b，那么这时 a (上一次的 b) 即为gcd
  return b == 0 ? a : gcd(b, a % b);
}

时间复杂度

  1. 考虑 时，
  2. 考虑 时， 至少会使 折半，那么次数为

因此时间复杂度为

多个数的最大公约数

对于多个数的最大公约数，也一定是每个数的约数，那么也一定是每相邻两个数的约数。
我们采用归纳法，可以证明，每次取出两个数求出答案后再放回去，不会对所需要的答案造成影响。

最小公倍数 - Least Common Multiple

原理

设，

其中 是素因子，是相应的幂
容易证得


那么有
因此

因而要求最小公倍数，只需知道 与其最大公约数 ，即

实现

1
2
3
int lcm(int x, int y) {
  return x / gcd(x, y) * y;
}

多个数的最小公倍数

对于多个数的最小公倍数，也一定是每两个数的最小公倍数，所以与多个数的最大公约数求法类似，每次取出两个数求其最小公倍数后再放回去，直到只剩一个数，即为最小公倍数