整除

定义： $a，b ∈ Z$ ，$b ≠0$。如果有一个整数 $q$，使得 $a=bq$，则 $a$ 叫做 $b$ 的倍数，$b$ 叫做 $a$ 的因数。或者说 $b$ 能整除 $a$ 或者 $a$ 能被 $b$ 整除，记作 $b | a$。

如果 $b$ 不能整除 $a$，记作 $b ∤ a$。

引理：

若 $a，b，c ∈Z$ ，而 $a | b，b | c$，则 $a | c$。

证：$b = aq_1$，$c = bq_2$ ⇒ $c=a(q_1q_2)$

引理：

证： $a，b ∈Z$，若 $|a| < |b|$，$|b| | |a|$，则 $a=0$。

如果 $|a|>0，0<|a|<|b|，|a|=|b|q$，如果 $q>0$，由于 $q ∈ Z$，$q ≥1$。

则 $|a| ≥|b|$，与 $|a|<|b|$ 矛盾，所以 $|a|=0$。

引理：

带余除法：若 $a，b ∈Z，b≠0$，则一定有且只有两个整数 $q，r$，使得 $a = bq+r$，$0 ≤r<|b|$。

证：

1. 存在有一个整数 $q$，使得 $a=bq$，故 $r=0$，本引理成立。
2. $a = bq+r$，$0 ≤r<|b|$ 式子1

假设还有另外一对 $a=bq_1+ r_1$， $0 ≤r_1<|b|$ 式子2

两式相减，$0=b(q- q_1)+(r - r_1)$ 式子3

$|b| | | r - r_1 |$

$| r - r_1 |<|b|$

⇒ $r - r_1=0$

⇒ $r = r_1$

由式子3 和 $b≠0 ⇒ q =q_1$

最大公约数

定义：如果 $n ∈Z$，$n ≥2$，而 $a_1，a_2，⋅⋅⋅，a_n，d$ 都是正整数，又设 $d|a_1，d|a_2⋅⋅⋅d|a_n$ 则 $d$ 叫做 $a_1，a_2，⋅⋅⋅，a_n$ 的公约数，公约数中最大的一个叫做最大公约数，最大公约数是其他所有公约数的倍数，记作 $(a_1，a_2，⋅⋅⋅，a_n)=d$。

引理： $a，b$ 都是正整数，且 $a>b$，$a=bq+r$，$0<r<b$ ，其中 $q$ 和 $r$ 都是正整数，则 $a$ 和 $b$ 的最大公约数等于 $b$ 和 $r$ 的最大公约数，即 $(a,b)=(b,r)$。

辗转相除法举例

求 $6731$ 和 $2809$ 的最大公因数：

$6731 = 2809*2 + 1113$

$2809 = 1113*2 + 583$

$1113 = 583*1 + 530$

$583 = 530 + 53$

$530 = 53*10 + 0$

所以 $(6731,2809)= 53$

int gcd(int a, int b){
    return b ? gcd(b, a % b) : a;
}

复杂度为 $O(log(max(a,b))$。

由于任何正整数都是 $0$ 和 $0$ 的公约数，故 $gcd(0, 0)$ 不存在。

对任意正整数 $a$，有 $gcd(0, a) = a$。

二进制算法：不断去除因子 $2$ 来降低常数。

int gcd(int a, int b){
	if(a == b) return a;
	if(a < b) return gcd(b, a);
	if(a % 2 == 0 && b % 2 == 0) return 2 * gcd(a / 2, b / 2);
	if(a % 2 == 0 && b % 2) return gcd(a / 2, b);
	if(a % 2 && b % 2 == 0) return gcd(a, b / 2);
	if(a % 2 && b % 2) return gcd(b, a - b);
}

最小公倍数

设 $a,b$ 为正整数，$m$ 为非负整数，若 $a | m$ 且 $b | m$，则称 $m$ 为 $a$ 和 $b$ 的公倍数。

$a$ 和 $b$ 的所有公倍数中最小的正数称为 $a$ 和 $b$ 的最小公倍数，记为 $lcm(a, b)$。

根据定义，显然有 $lcm(a,b)= lcm(b,a)$。

lcm和gcd关系：$lcm(a,b)=\frac{ab}{gcd(a,b)}$

需要注意的是，在实际的代码实现中，为避免中间结果的溢出，应该使用 $a/gcd(a,b)*b$，而不是 $a*b/gcd(a,b)$。

算数基本定理（唯一分解定理）

设 $n≥2$ 为整数，则有唯一的分解式：$n = \prod\limits_{i=1}^m {P_i}^{\alpha_i}$，其中 $P_1<P_2<...<P_m$ 且 $P_i$ 为质数，$\alpha_i$ 为正整数。

约数个数定理

$n$ 的约数个数 $d(n) = \prod\limits_{i=1}^m (\alpha_i+1)$

例如：$28=2^2 \times 7$

$d(28)=(2+1) \times (1+1)=6$

$n$ 的约数和 $S_n=(1+p_1+p_1^2+...+p_1^{\alpha_1})(1+p_2+p_2^2+...+p_2^{\alpha_2})...(1+p_k+p_k^2+...+p_k^{\alpha_k})$

$S(28)=(1+2+4)(1+7)=56$

裴蜀定理

对于不定方程 $ax+by=m$, 其有解的充要条件 $gcd(a,b) | m$。

重要推论：当 $a$，$b$ 互质时，$a$，$b$ 的整系数线性组合可以得到所有的整数。

质数与合数

定理：一个大于 $1$ 的正整数，只能被 $1$ 和自身整除，不能被其他正整数整除，这样的正整数叫做质数。

一个正整数，除了能被 $1$ 和自身整除外，还可以被其他的正整数整除，这样的正整数叫做合数。

如果一个正整数 $a$ 有一个因数 $b$，而 $b$ 又是质数，则 $b$ 就叫做 $a$ 的质因数。

全体正整数可以分为 3 类：

1. 整数 $1$
2. 全体质数
3. 全体合数

引理：如果 $a$ 是一个大于 $1$ 的整数，则 $a$ 的大于 1 的最小因数一定是质数。

证：

1.如果 $a$ 是一个质数，$a$ 的大于 $1$ 的因数只有一个，就是 $a$，结论成立。

2.如果 $a$ 是一个合数，除 $1$ 和 $a$ 之外，$a$ 还有其他正因数，假设 $b$ 是这些正因数中最小的，假定 $b$ 是合数，一定有 $1<c<b$，$c|b$，$b|a$，即 $c|a$，与假设矛盾。

此引理说明了：任何大于 $1$ 的整数都至少有一个质因数。

质因数分解

题目描述

已知正整数 $n$ 是两个不同的质数的乘积，试求出两者中较大的那个质数。

输入格式

一个正整数 $n$。$(n≤2×{10}^9)$

输出格式

一个正整数 $p$，即较大的那个质数。

21

7

参考程序：

#include <iostream>
using namespace std;

int main() {

    int n;
    cin >> n;
    for (int i = 2; i <= n; i++) {
        if (n % i == 0) {
            cout << n / i << endl;
            break;
        }
    }
        
	return 0;
}

引理：如果 $a$ 是一个大于 $1$ 的整数，而所有 ≤$\sqrt{a}$ 的数都除不尽 $a$，则 $a$ 是质数。

质数个数定理：定义 $π(x)$ 为不大于 $x$ 的质数的个数，$\lim\limits_{n\to\infty} \frac{π(x)}{\frac{x}{logx}}=1$

筛法求质数

朴素筛法：枚举 $2$ 到 $n$ 的每个数 $i$，将 $2i，3i，···$ 均标记为合数；

枚举完后仍没有被标记的数即为质数。

时间复杂度：$O(\sum\limits_{i=1}^n \frac{n}{i})=O(nlogn)$

简要证明：调和级数前 $n$ 项和 $≈logn$

$f(n)=\sum\limits_{i=1}^n \frac{1}{i}=(\frac{1}{1})+(\frac{1}{2}+\frac{1}{3})+(\frac{1}{4}+\frac{1}{5}+\frac{1}{6}+\frac{1}{7})+...$

vector<int> get_primes(int n){
	vector<int> v;	
    for(int i = 2; i <= n; i++){
    	if(!book[i]) v.push_back(i);
        
        for(int j = 2 * i; j <= n; j += i)
            book[j] = true;
    }
    return v;
}

埃式筛法：（Eratosthenes筛法）只有质数才可能标记后面的合数。

时间复杂度：$O(nloglogn)$。

vector<int> get_primes(int n){

	vector<int> v;	
    
    for(int i = 2; i <= n; i++){
    	if(!book[i]) {
            v.push_back(i);
            
            for(int j = 2 * i; j <= n; j += i)
            	book[j] = true;
        } 
    }
    
    return v;
}

欧拉筛法：（线性筛法）设 $x$ 的最小质因数为 $d$，则 $x$ 只会被 $\frac{x}{d}$ 标记。

时间复杂度 $O(n)$。

当枚举到 $i$ 时，假设当前已经求出质数为 $P_1，P_2，… P_k$，而 $i$ 的最小质因数为 $P_m$，则对于所有的 $x∈[1,m]$，$P_x i$ 的最小质因数就是 $P_x$，故用 $i$ 标记 $P_x i$。

vector<int> get_primes(int n){
	vector<int> v;
  	for(int i = 2; i <= n; i++){
    	if(!book[i]) v.push_back(i);
      	for(int j = 0; v[j] <= n / i; j++){
        	book[v[j] * i] = true;
          	if(i % v[j] == 0) break;
        }
    }
  	return v;
}

集合论

集合与元素

集合：是由确定的对象（客体）构成的集体

元素：集合中的对象，称之为元素

集合与元素的关系：$\in$ 和 $\notin$

集合的表示方法

列举法：$A = \{a, b, c, d\}$

描述法：$B = \{x \thinspace | \thinspace x \thinspace is \thinspace even\}$

有限集和无限集

有限集合：元素是有限个的集合。

如果 $A$ 是有限集合，用 $|A|$ 表示 $A$ 中的个数。

例如：$A = \{1, 2, 3\}$，则 $|A| = 3$

无限集合：元素是无限个的集合。

例如：所有自然数 $N$ 构成的集合是无限集合。

包含关系

定义：$A、B$ 是集合，如果 $A$ 中元素都是 $B$ 中元素，则称 $B$ 包含 $A$，$A$ 包含于 $B$，也称 $A$ 是 $B$ 的子集。记 $A⊆B$。

例如：$N$ 是自然数集合，$R$ 是实数集合，则 $N⊆R$。

韦恩图：又叫文氏图，可以用来表示集合关系。

韦恩图是用固定位置的交叉形式的封闭曲线内部的区域来表示集合及其关系的图形。

真被包含关系 定义：$A、B$ 是集合，如果 $A⊆B$ 且 $A≠B$，则称 $B$ 真包含 $A$，$A$ 真包含于 $B$，也称 $A$ 是 $B$ 的真子集，记作 $A⊂B$。

子集关系性质

自反性：对任何集合 $A$ 有 $A⊆A$。

传递性：对任何集合 $A、B、C$，有 $A⊆B$ 且 $B⊆C$，则 $A⊆C$。

反对称性：对任何集合 $A、B$，有 $A⊆B$ 且 $B⊆A$，则 $A=B$。

特殊集合

全集：包含所讨论的所有集合的集合的集合，称之为全集，一般记作 $E$ 或 $I$。

空集：没有元素的集合，称之为空集，记作 $Ø$。

• 任何元素 $x$ 都不属于 $Ø$。
• 空集是任何集合的子集。即对于任何集合 $A$，都有 $Ø∈A$。
• 空集是唯一的。
• 比如集合 $A=\{1, 2\}$，子集有 $4$ 个，$\{1\}，\{2\}，\{1, 2\}$，和 $Ø$。

集合的幂集：$A$ 是集合，由 $A$ 的所有子集构成的集合，称之为 $A$ 的幂集。记作 $P(A)$ 或 $2^A$。

给定有限集合 $A$，如果 $|A|=n$，则 $|P(A)|=2^n$

补集：$A$ 是集合，由不属于 $A$ 的元素构成的集合称之为 $A$ 的补集，记作 ~$A$。

集合运算

集合交换律：$A∩B=B∩A$；$A∪B=B∪A$。

集合结合律：$(A∩B)∩C=A∩(B∩C)$；$(A∪B)∪C=A∪(B∪C)$。

集合分配律：$A∩(B∪C)=(A∩B)∪(A∩C)$；$A∪(B∩C)=(A∪B)∩(A∪C)$。

容斥原理

在计数时，必须注意不重不漏，为了使重叠部分不被计算，我们需要使用容斥原理。

基本思想：对包含对象的集合中所有对象数目求和，再把重复计算的排斥出去。

两集合容斥原理：如果有 $A、B$ 两个有限集合，则 $|A∪B|=|A|+|B|-|A∩B|$。

三集合容斥原理：如果有 $A、B、C$ 三个有限集合，则 $|A∪B∪C|=|A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C|$。

等差数列

对于数列 $\{a_n\}$，若满足：

$\begin{cases}a_n-a_{n-1}=d\\n \in N\\d \in R\end{cases}$

则称该数列为等差数列。其中，公差 $d$ 为实数，$n$ 为正整数。

求等差数列第 $n$ 项：$a_n=a_1+(n-1) \times d$

等差数列前 $n$ 项和 $S_n=\frac{(a_1+a_n) \times n}{2}$

等比数列

对于数列 $\{a_n\}$，若满足：$\frac{a_n}{a_{n-1}} =q(n≥2,a_{n-1}≠0,q≠0)$，则称该数列为等比数列。

求等比数列第 $n$ 项：$a_n=a_1 \times q^{n-1}$

等比数列前 $n$ 项和：

$S_n=\begin{cases}n \times a_1&q=1\\ \frac{a_1 \times (1-q^n)}{1-q}& q≠1\end{cases}$

平面直角坐标系

任意两点 $p_1 (x_1,y_1)$ ，$p_2 (x_2,y_2)$之间的距离:

$|p_1p_2|=\sqrt{(x_1-x_2)^2-(y_1-y_2)^2}$

点 $p_1 (x_1,y_1)$ 到直线 $Ax+By+C=0$ 之间的距离：$\frac{|Ax_1+By_1+C|}{\sqrt{A^2+B^2}}$

点 $p_1 (x_1,y_1)$ 到直线 $y=kx+b$ 之间的距离：$\frac{|kx_1-y_1+b|}{\sqrt{1+k^2}}$

三角形

内角和：180°

判定：任意两边之和大于第三边。

面积公式：

1.已知三角形底为 $a$，高为 $h$，则 $S=\frac{ah}{2}$

2.(海伦公式）已知三角形三边 $a,b,c$，则 $p=\frac{a+b+c}{2}$, $S=\sqrt{p(p-a)(p-b)(p-c)}$

多边形

$n$ 边形内角和：$(n-2) \times 180^。$

判定：任意 $(n-1)$ 边之和大于第 $n$ 边。（最长边小于其他边之和）

常见多边形面积公式：

1. 长方形（正方形）：已知长方形长为 $a$，宽为 $b$，$S=a \times b$
2. 平行四边形：已知平行四边形底为 $a$，高为 $h$，$S=a \times h$
3. 梯形：已知梯形上底 $a$，下底为 $b$，高为 $h$，$S=\frac{(a+b) \times h}{2}$

圆

常见关于圆的公式（已知圆的半径 $r$）：

1. 直径：$d=r \times 2$
2. 周长：$C=2 \times r \times π$
3. 面积：$S=π \times r^2$

补充：

• 球的体积：$V=\frac{4}{3}πr^3$
• 圆柱体积：$V=πr^2h$

排列组合

排列：从给定个数的元素中取出指定个数的元素进行排序。

从 $n$ 个不同元素中，任取 $m$ 个不同的元素按照一定的顺序排成一列，叫做从 $n$ 个不同元素中取出 $m$ 个元素的一个排列；从 $n$ 个不同元素中取出 $m(m≤n)$ 个元素的所有排列的个数，叫做从 $n$ 个不同元素中取出 $m$ 个元素的排列数。

用符号 $A(n, m)$ 或 $A_n^m$ 表示。

$A_n^m=n(n-1)(n-2)...(n-m+1)=\frac{n!}{(n-m)!}$

组合：从给定个数的元素中仅仅取出指定个数的元素，不考虑排序。

从 $n$ 个不同元素中，任取 $m(m≤n)$ 个元素并成一组，叫做从 $n$ 个不同元素中取出 $m$ 个元素的一个组合；从 $n$ 个不同元素中取出 $m(m≤n)$ 个元素的所有组合的个数，叫做从 $n$ 个不同元素中取出 $m$ 个元素的组合数。用符号 $C(n,m)$ 或 $C_n^m$ 表示。

$C_n^m=\frac{A_n^m}{m!}=\frac{n!}{m!(n-m)!}$

$C_n^m=C_n^{n-m}$，其中 $n≥m$

加法原理和乘法原理

加法原理：是分类计数原理，常用于排列组合中，具体是指：做一件事情，完成它有 $n$ 类方式，第一类方式有 $M_1$ 种方法，第二类方式有 $M_2$ 种方法，……，第 $n$ 类方式有 $M_n$ 种方法，那么完成这件事情共有 $M_1+M_2+……+M_n$ 种方法。

例：改密码问题

原密码为 abcdefg，现有两种改密码的方法。

方法一：将其中一个字母改为大写

方法二：在最后加一个数字

一共有多少种方案？

两种方法互不干扰，采用分类加法：

1. 一共 7 个字母，有 7 种方案
2. 一共 10 个数字，有 10 种方案

10+7=17 种

乘法原理：做一件事，完成它需要分成 $n$ 个步骤，做第一 步有 $m_1$ 种不同的方法，做第二步有 $m_2$ 种不同的方法，……，做第 $n$ 步有 $m_n$ 种不同的方法。那么完成这件事共有 $N=m_1×m_2×m_3×…×m_n$ 种不同的方法。

例：三件上衣，两条裤子，有多少种搭配？

先选上衣，再选裤子，采用分步乘法：2×3=6 种

例：密码锁

有一密码箱，左右分别有两个锁，每个锁密码都是三位数，每位数有 $0$~$9$ 十个数字。请问如果想要暴力枚举破解密码，最差的情况下需要试多少次？

对于每个密码锁的三位密码，采用分步乘法原理，则为：$10×10×10=1000$ 种。

两个密码锁之间互不干扰，采用分类加法原理，则为：$1000+1000=2000$ 种。

常见问题

捆绑法：$7$ 个学生站成一排，甲、乙必须站在一起有多少种排法？

• 将甲、乙捆绑在一起
• $A_6^6 \times 2 = 1440$

插空法：$7$ 个学生站成一排，甲、乙互不相邻有多少种排法？

• 把甲、乙单独拿出来，剩下5名学生有6个空隙
• $A_5^5 \times A_6^2 = 3600$

排除法：重新排列 $1234$ 使得每一个数字都不在原来的位置上，一共有多少种排法？

• $4$ 个数字都在原来位置：$1234$
• $3$ 个数字都在原来位置：没有
• $2$ 个数字都在原来位置：$1243$ $1432$ $1324$ $4231$ $3214$ $2134$
• $1$ 个数字在原来位置：$1423$ $1342$ $4213$ $3241$ $4132$ $2431$ $3124$ $2314$
• $A_4^4 – 15 = 4 \times 3 \times 2 \times 1 – 15 = 9$

鸽巢问题：又称抽屉原理，最先是由 $19$ 世纪的德国数学家狄利克雷提出来的所以又称狄里克雷原理，这一原理在解决实际问题中有着广泛的应用。

$6$ 只鸽子飞回 $5$ 个鸽舍，至少有 $2$ 只鸽子要飞进同一个鸽舍里，为什么？

至少数=商+1=6/5+1=2

随堂检测

1.一次期末考试，某班有 $15$ 人数学得满分，有 $12$ 人语文得满分，并且有 $4$ 人语、数都是满分，那么这个班至少有一门得满分的同学有（ ）人。

{{ select(1) }}

• $23$
• $21$
• $20$
• $22$

2.在 $1$ 和 $2015$ 之间（包括 $1$ 和 $2015$ 在内）不能被 $4、5、6$ 三个数任意一个数整除的数有（ ）个。

{{ select(2) }}

• $1073$
• $1074$
• $1075$
• $1076$

3.某班有 $50$ 名学生，每位学生发一张调查卡，上写着$a,b,c$ 三本书的书名，将读过的书打 √，结果统计数字如下：只读 $a$ 者 $8$ 人；只读 $b$ 者 $4$ 人；只读 $c$ 者 $3$ 人；全部读过的有 $2$ 人；读过 $a，b$ 两本书的有 $4$ 人；读过 $a，c$ 两本书的有 $2$ 人；读过 $b，c$ 两本书的有 $3$ 人；

（1）读过 a 的人数是（ ）

（2）一本书也没有读过的人数是（ ）。

{{ select(3) }}

• $12,30$
• $12,32$
• $8,30$
• $8,32$

4.10000 以内，与 10000 互质的正整数有（ ）个。

{{ select(4) }}

• 2000
• 4000
• 6000
• 8000

5.设含有 10 个元素的集合的全部子集数为 S，其中由 7 个元素组成的子集数为 T，则 T/S 的值为（ ）。

{{ select(5) }}

• $\frac{5}{32}$
• $\frac{15}{128}$
• $\frac{1}{8}$
• $\frac{21}{128}$

6.班上有 $9$ 位同学，现在要选出 $2$ 位纪律委员和 $1$ 位班长，共有多少种选法（ ）。

{{ select(6) }}

• $252$
• $256$
• $258$
• $128$

7.黑猫老师在书店看中 $4$ 本 C++ 书和 $3$ 本数学书，但他只能各买 $2$ 本，并且他希望每周看完 $1$ 本书，请问他有多少种安排方式（ ）。

{{ select(7) }}

• $18$
• $24$
• $216$
• $432$

8.在书架上放有编号 $1，2，…，n$ 的 $n$ 本书。现将 $n$ 本书全部取下然后再放回去，当放回去时要求每本书都不能放在原来的位置上。

例如，$n=3$ 时，原来位置为：$1$ $2$ $3$；

放回去时只能为：$3$ $1$ $2$ 或 $2$ $3$ $1$ 这两种。

问题：当 $n=5$ 时满足以上条件的放法共有（ ）种。

{{ select(8) }}

• $42$
• $43$
• $44$
• $45$

9.从 $1$ 到 $2018$ 这 $2018$ 个数中，共有（ ）个包含数字 8 的数。

{{ select(9) }}

• $541$
• $542$
• $543$
• $544$

10.有 $7$ 个一模一样的苹果，放到 $3$ 个一样的盘子中，一共有（ ）种放法。

{{ select(10) }}

• $7$
• $8$
• $21$
• $3^7$