初等数论

M1__ · 2024-08-24 09:39:22 · 算法·理论

初等数论

初等数论概念

• 若整数 b 除以非零整数 a（b 为被除数，a 为除数）的余数为 0，则称 a 整除 b 或 b 能被 a 整除。记作 a\mid b，a 叫做 b 的约数（因数），b 叫做 a 的倍数。

• - 当 $b=2$ 时，称为 $a$ 的平方； - 当 $b=3$ 时，称为 $a$ 的立方； - 另外，$a^0=1$，$a^b(b<0)= \frac{1}{a^{-b}}$。

• 素数（质数）、合数

  • 对于一个整数 n(n \ge 2) 如果除了 1 和它本身以外不再有其他约数，则称 a 为素数（质数）。
  • 相反地，对于一个整数 n(n \ge 2)，如果除了 1 和它本身以外还有其他约数，则称 n 为合数。
  • 另外，1 既不是质数也不是合数。
  • 唯一分解定理：对于任意一个合数 n，都可以分解成有限个质数的乘积。

• 最大公约数和最小公倍数

  • 最大公约数指的是两个或多个整数共有约数中最大的一个，a 和 b 的最大公约数记为 (a,b)。
  • 最小公倍数指的是两个或多个整数除以 0 以外的共有倍数中最小的一个，a 和 b 的最小公倍数记为 [a,b]。
  • 另外，[a,b]=\frac{a \times b}{(a,b)}。

• 如果两个正整数 a 和 b 除以正整数 p 的余数相同，则称 a 与 b 对模 p 同余，记作 a \equiv b(\bmod\ p)。

  C++ 中的数学函数

• 最大值函数 max(a,b)；

• 最小值函数 min(a,b)；

• 绝对值函数 abs(x)；

  • 对于绝对值，有如下性质：
  -x,x<0 \\ 0,x=0\\ x,x>0 \end{matrix}\right.

• 向下取整函数 floor(x)；

• 向上取整 ceil(x)；

• 四舍五入函数 round(x)；

• 平方根函数 sqrt(x)；

• 常用三角函数 sin(x)，cos(x)，tan(x)；

• 对数函数 long(x)；

• 指数函数 pow(a,b)；

  加法原理和乘法原理

• 加法原理

  • 做一件事情，完成它有 n 种方式，第一类方式有 m_1 种方法，第二类有 m_2 种方法，第 n 类方式有 m_n 种方法，那么完成这件事情共有 m_1+m_2+ \cdots +m_n 种方法。
  • 比如说：从武汉到上海有乘火车、飞机、轮船 3 种交通方式可供选择，而火车、飞机、轮船分别有 k_1,k_2,k_3 个班次，那么从武汉到上海共有 k_1+k_2+k_3 种不同的选择可以到达。

• 乘法原理

  • 做一件事情，完成它需要分成 n 个步骤，做第一步有 m_1 种不同的方法，做第二步有 m_2 种不同的方法，做第 n 步有 m_n 种不同的方法。那么完成这件事共有 N = m_1 \times m_2 \times m_3 \times \cdots \times m_n 种不同的方法。

    容斥原理

• ## 排列组合 ### 排列

• 排列：从 n 个不同元素中取出 m(m \le n) 个元素，按照一定的熟悉排成一列，叫做从 n 个元素中取出 m 个元素的一个排列。

• 从 n 个不同元素中取出 m(m \le n) 个元素的所有不同排列的个数称为排列数，记作 P^m_n 或 A^m_n。

  P^m_n=A^m_n=n(n-1)(n-2) \cdots (n-m+1)=\frac{n!}{(n-m)!}

  组合

• 从 n 个不同的元素中取 m(m \le n) 个元素为一组。叫做从 n 个不同元素中取出 m 个元素的一个组合。

• 注意，在组合中，取元素的顺序是无所谓的。

• 从 n 个不同的元素取 m(m \le n) 个元素的所有不同组合的个数称为组合数。记作 C^m_n 或\begin{pmatrix} n\\ m \end{pmatrix}。

• 特殊性质：

另外，还有一些公式：

• 从 n 个不同的元素取 m 个元素（可以重复取）的排列个数为 n^m。
• 把 n 个相同的元素分成 m 个不同的组，每组至少有一个元素的方案数位 C^{m-1}_{n-1}。
• 把 n 个相同的元素分成 m 个不同的组，每组可以一个元素也没有的方案数为 C^{m-1}_{n+m-1}。（隔板法）
• 从 n 个不同的元素中取 m 个元素（元素可以重复取）的组合个数为 C^{n-1}_{n+m-1}。