标签：frac 数论 不同 元素 整数 times cdot 初等
6. 初等数论
6.1 初等数论概念
- 若整数 \(b\) 除以非零整数 \(a\) （ \(b\) 为被除数， \(a\) 为除数）的余数为 \(0\) ，则称 \(a\) 整除 \(b\) 或 \(b\) 能被 \(a\) 整除。记作 \(a\ |\ b\) , \(a\) 叫做 \(b\) 的约数（因数）， \(b\) 叫做 \(a\) 的倍数。
- \(a^b\) ( \(b\) 位非负整数) 表示 \(b\) 个 \(a\) 相乘，其中 \(a\) 为底数， \(b\) 为指数。
- 当 \(b=2\) 时，称为 \(a\) 的平方；
- 当 \(b=3\) 时，称为 \(a\) 的立方；
- 另外， \(a^0=1\) , \(a^b\ (b<0)=\frac{1}{a^{-b}}\)
- 素数（质数）、合数
- 对于一个整数 \(n\ (n>=2)\) 如果除了 \(1\) 和它本身以外不再有其他约数，则称 \(a\) 为素数（质数）。
- 相反地，对于一个整数 \(n\ (n>=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\ (\mod p)\) 。
6.2 C++中的数学函数
- 最大值函数
max(a,b) ;
- 最小值函数
min(a,b) ;
- 绝对值函数
abs(x) ;
\[|x|\left\{\begin{matrix}
|x|=-x\ (x<0) \\
|x|= 0\ (x=0) \\
|x|=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) ;
6.3 加法原理和乘法原理
- 加法原理
- 做一件事情，完成它有 \(n\) 种方式，第一类方式有 \(m_1\) 种方法，第二类有 \(m_2\) 种方法，第 \(n\) 类方式有 \(m_n\) 种方法，那么完成这件事情共有 \(m_1+m_2+\cdot \cdot \cdot +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 \cdot \cdot \cdot \times m_n\) 种不同的方法。
6.4 容斥原理
- \(\cup\) , 并集，表示满足 \(A\) 或 \(B\) 任意一个。
- \(\cap\) ，交集，表示同时满足 \(A\) 和 \(B\) 。
6.5 排列组合
6.5.1 排列
- 排列：从 \(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)...(n-m+1)=\frac{n!}{(n-m)!}
\]
6.5.2 组合
- 从 \(n\) 个不同的元素中取 \(m\ (m \le n)\) 个元素为一组。叫做从 \(n\) 个不同元素中取出 \(m\) 个元素的一个组合。
- 注意，在组合中，取元素的顺序是无所谓的。
- 从 \(n\) 个不同的元素取 \(m \ (m \le n)\) 个元素的所有不同组合的个数称为组合数。记作 \(C^m_n\) 或 \(\begin{pmatrix}
n\\
m
\end{pmatrix}\)
\[c^m_n=\frac{p^m_n}{m!}=\frac{n(n-1)(n-2)...(n-m+1)}{m!}=\frac{n!}{m!(n-m)!}
\]
- 特殊性质：
- \(C^0_n=1\) ;
- \(C^m_n=C^{n-m}_n\) ;
- \(C^m_n=C^{m-1}_{n-1}+C^{m}_{n-1}\) ;
另外，还有一些公式：
- 从 \(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}\)
标签：frac,
数论,
不同,
元素,
整数,
times,
cdot,
初等
From： https://www.cnblogs.com/M1--1e9/p/18377413