初等数论

关于取余与取模

在很多时候，我们把 % 也称作模运算符。那取余和取模有什么区别吗？如果有区别，C++ 中的 % 到底是指的取余运算还是取模运算？

在初等数论中，取余与取模运算还是有区别的。

取余（rem），遵循尽可能让商向 0 靠近的原则
取模（mod），遵循尽可能让商向负无穷靠近的原则

也就是说，当商为正数（运算的两个数同号）时，取余与取模是一致的；当商为负数（运算的两个数异号）时，取余与取模的行为就不一致了。

通过一个例子来看更容易理解。

例如，5 rem 2，余数是 1 。对于 5 mod 2，由于在数学上 5 除以 2 的商为 2.5，要遵循商尽可能向 0 靠近的原则，商应该取 2，那取模运算的结果应该是 5 - 2 * 2 = 1 。

在 C/C++ 中，% 为取余（rem）运算。在 Python 中 % 为取模运算，这一点一定要区分开来。

整除/因数/倍数/指数/质数/合数

最大公约数

最大公约数（Greatest Common Divisor，GCD），又称最大公因数或最大公因子，是指几个自然数公共的因数中最大的一个。

例如：30 和 18 的公约数有 1、2、3、6，其中最大的是 6，因此 6 是 30 和 18 的最大公约数。

辗转相除法（又称欧几里得算法） 是一种求两个整数最大公约数的高效方法。

辗转相除法基于一个简单的递归公式：两个数的最大公约数等于其中较小的那个数和两数相除的余数的最大公约数。

仍然以求 30 和 18 的最大公约数为例。

30 % 18 = 12
18 % 12 = 6
12 % 6 = 0 （余数为 0，停止计算，最大公约数为 6）

感兴趣的可以自行去证明一下为什么辗转相除法（欧几里得算法）可以用于求最大公约数

代码实现

下面是通过辗转相除法去求最大公约数的两种实现方式。

方法一：

根据辗转相除法的定义，利用递归实现，参考代码如下。

#include <iostream>
using namespace std;

int gcd(int x, int y) {
  if (y == 0) return x;
  else return gcd(y, x % y);
}

int main() {
  int a, b;
  cin >> a >> b;

  cout << gcd(a, b) << endl;
  return 0;
}

当然，也可以不用递归实现，做一个简单的变量交替代换，参考代码如下。

#include <iostream>
using namespace std;

int gcd(int x, int y) {
  while (y != 0) {
    int r = x % y;
    x = y;
    y = r;
  }

  return x;
}

int main() {
  int a, b;
  cin >> a >> b;

  cout << gcd(a, b) << endl;
  return 0;
}

最小公倍数

对于两个整数 a 和 b，如果有另外一个数，既是 a 的倍数，也是 b 的倍数，那这个数就是 a 和 b 的公倍数，所有公倍数中最小的，就被称为最小公倍数（Least Common Multiple, LCM）。

代码实现

方法一：枚举求解

根据定义，我们可以用枚举（暴力）的方法去计算最小公倍数，也就是让计算机一个一个去试，最差的情况下，a 和 b 的乘积 a * b 一定是 a 和 b 的公倍数，因此尝试的范围在一定在 1 ~ a * b 之间。

可以从两个数中较大的一个开始，逐一检查其倍数是否为另一个数的倍数，直到找到最小的公共倍数为止。

参考代码如下。

#include <iostream>
using namespace std;

int lcm(int a, int b) {
  int mx = (a > b) ? a : b;

  for (int i = mx; i <= a * b; i++) {
    if ( i % a == 0 && i % b == 0) {
      return i;
    }
  }
}

int main() {
    int n, m;
    cin >> n >> m;

    cout << lcm(n, m) << endl;

    return 0;
}

用枚举的方法来求最小公倍数是一种直观但效率较低的方法，尽管效率不高，但可以通过这种方式帮助我们更好的理解 LCM 的基本概念。

方法二：利用最大公约数求解

这种方法主要是利用最小公倍数（LCM）与最大公约数（GCD）之间的一个关联公式，公式如下：

$LCM(a, b) = \frac{|a \times b|}{GCD(a, b)}$

前面我们已经通过辗转相除法实现了最大公约数的求解，因此直接利上面的关联公式就可以求出最小公倍数。参考代码如下：

#include <iostream>
using namespace std;

// 计算两个整数的最大公约数（GCD）
int gcd(int x, int y) {
  while (y != 0) {
    int r = x % y;
    x = y;
    y = r;
  }

  return x;
}

// 计算两个整数的最小公倍数（LCM）
int lcm(int x, int y) {
  return (a * b) / gcd(a, b);
}

int main() {
  int a, b;
  cin >> a >> b;

  cout << lcm(a, b) << endl;
  return 0;
}

取整

模与同余

整数唯一分解定理

整数唯一分解定理，也称为算术基本定理，任何大于 1 的整数 n 有且只有一种方法将其分解成素因数（质因数）的连乘积，即：

$n=p_{1}^{\alpha_1}p_{2}^{\alpha_2}...p_{m}^{\alpha_m}, m \ge 1$

例如： $10=2 \times 5$ ，

将一个大于 1 的整数 $n$ 分解成质因数。

42qhjvqw8 - C++ - OneCompiler

#include <bits/stdc++.h>
using namespace std;

void dfs(int n, int p) {
  if (n == 1) return;
  if (n % p == 0) {
    cout << p << " ";
    dfs(n / p, p);
  } else {
    dfs(n, p + 1);
  }
}
int main() {
  int n;
  cin >> n;

  dfs(n, 2);
  return 0;
}

辗转相除法

素数筛法

接下来我们来探讨一下素数（Prime）这个主题，素数，又称质数，是数学中一个非常重要的概念，在计算机科学和密码学中都有广泛的应用。

为了配合本部分素数筛法的标题，以下的内容我们都会使用素数这个名称，不再使用质数。

素数是大于1的自然数中，除了1和它本身外不再有其他因数的数。换句话说，素数只能被1和它自身整除。

例如：2, 3, 5, 7, 11, 13, 17, 19, 23, 29…

在前面的 C++ 基础语法中，在循环的应用部分，已经有讲到如何求素数的方法。下面再来快速回顾一下。

朴素方法

求素数最相素、直观的方法是根据素数的定义，检查从 2 到 n - 1 的所有数，看是否能整除 n。

下面用朴素方法判断一个整数是否是素数的函数。

bool is_prime(int n) {
  if (n <= 1) return false;
  for (int i = 2; i < n; i++) {
    if (n % i == 0) return false;
  }
  return true;
}

这个方法简单直观，但效率较低。如果是要判断 n 个数中有哪些是素数，其算法的时间复杂度为 $O(n^2)$ 。

朴素方法优化

对于素数，有这样一个结论，如果一个数 n 不是素数，它一定有一个小于或等于 $\sqrt{n}$ 的因子。

这是因为，如果 $a \times b = n$ ，那么 $a$ 和 $b$ 中至少有一个小于或等于 $\sqrt{n}$ 。

利用这一点，我们可以优化上面求素数的函数：

bool is_prime(int n) {
  if (n <= 1) return false;
  for (int i = 2; i < sqrt(n); i++) {
    if (n % i == 0) return false;
  }
  return true;
}

这个优化大大减少了我们需要检查的数字数量，特别是对于大数来说，这个优化的效果非常显著。

当然，我们还可以继续优化，例如，除 2 之外，所有的偶数一定都不是素数，因此在判断素数时可以事先将所有偶数排除掉，利用这一点可以进一步优化我们的函数。

bool is_prime(int n) {
  if (n <= 1) return false;
  if (n == 2) return true; // 2 是质数
  if (n % 2 == 0) return false; // 所有偶数都不是素数

  for (int i = 2; i < sqrt(n); i++) {
    if (n % i == 0) return false;
  }
  return true;
}

通过这个优化，循环操作的次数又减少一半。

埃氏筛法

当我们需要找出一定范围内的所有素数时，逐个判断每个数是否为素数的方法效率不高。这时，我们可以使用一种叫做”筛法”的技术。

埃氏筛法（the Sieve of Eratosthenes，埃拉托斯特尼筛法），是一种古老而高效的判断素数的算法，主要用于找出一定范围内的所有素数。

埃氏筛法的核心思想是：从最小的素数开始，将其所有倍数标记为非素数，然后找到下一个未标记的数，将其所有倍数继续标记为非素数，如此反复，直到范围内的所有数都处理完。

埃氏筛法的操作步骤如下：

【TODO】

算法复杂分析

时间复杂度： $O(nlog logn)$ ，这比之前的方法要快得多。
空间复杂度： $O(n)$ ，因为我们需要一个布尔数组来标记每个数。

线性筛法

线性筛法，也称欧拉筛法，是一种比埃氏筛法更高效的素数筛选算法，它的时间复杂度为 $O(n)$ ，这也正是为什么它被称为 “线性” 筛法的原因。

在埃氏筛法中，有些合数是被重复筛除多次。例如 6，会被 2 筛除一次，又会被 3 筛除一次。而在线性筛法中，每个合数只被最小的质因子筛除，每个合数只被筛除一次。

线性筛法算法中，有一句关键的代码：

if (i * primes[j] == 0) break;

这句代码确保了在找到 i 的最小质因子后，就停止继续标记。

为了帮助我们理解为什么线性筛法能保证每个合数只能被其最小质因子筛掉，下面我们来深入分析一下线性筛法的工作原理。

首先，我们需要理解，每个合数都可以唯一地表示为其最小质因子与另一个数的乘积。例如：

12 = 2 * 6
15 = 3 * 5
18 = 2 * 9

在这些例子中，2、3、2 分别是合数 12、15、18 的最小质因子。

再来看，为什么每个合数只被其最小的质因子筛掉。

考虑数字 12，它可以被表示为：

12 = 2 * 6
12 = 3 * 4

在筛法过程中：

当 i = 2 时，会标记它的倍数 4、6、8、10、12 …
当 i = 3 时，会标记它的倍数，先标记 9，尝试标记 12，但 12 已经被标记了
当 i = 4 时，会尝试用 2 去标记 8

初等数论

关于取余与取模

整除/因数/倍数/指数/质数/合数

最大公约数

代码实现

最小公倍数

代码实现

方法一：枚举求解

方法二：利用最大公约数求解

取整

模与同余

整数唯一分解定理

辗转相除法

素数筛法

朴素方法

朴素方法优化

埃氏筛法

算法复杂分析

线性筛法

小结