蒟蒻的学习笔记，时不时拿出来看一看。

数论

最大公约数

gcd(a, b) = gcd(b, a % b)

1
2
3
4
5
6
7
8
9

int gcd(int a, int b) {
    int mod;
    while(b > 0) {
        mod = a % b;
        a = b;
        b = mod;
    }
    return a;
}

最小公倍数

1
2
3

int lcm(int a, b) {
    return a * b / gcd(a, b);
}

互质数

互质数为数学中的一种概念，即两个或多个整数的公因数只有1的非零自然数。公因数只有1的两个非零自然数，叫做互质数。

基本不等式

$$a+b \geq 2 \sqrt{ab}$$

算数基本定理

任何一个大于1的正整数都能唯一分解成有限个质数的乘积，可以写作：
$$N = p_1^{c_1}p_2^{c_2}p_3^{c_3} \cdots p_m^{c_m}$$
其中$p_1,p_2,p_3 \cdots p_i$都是质数且递增，$c_i$都是正整数。

基本算数定理的推论

• $N$的正整数合集为$p_1^{b_1}p_2^{b_2}p_3^{b_3} \cdots p_m^{b_m}$，其中$0 \leq b_i \leq c_i$。

• $N$的正约数个数为$\prod^m_{i=1}(c_i+1)$。

• $N$的所有正约数的和为$(1+p_1+{p_1}^2+ \cdots +{p_1}^{c_1}) \times \cdots \times ((1+p_m+{p_m}^2+ \cdots +{p_m}^{c_1}) = \prod^m_{m=1}(\sum^{c_i}_{j=0}(p_m)^j)$。

欧拉函数

两个数的gcd等于$1$，即两个数互质。

$1$到$n$中与$n$互质的数的个数成为欧拉函数记$\phi(n)$。

$$\phi(n) = N \times \frac{p^1-1}{p^1} \times \frac{p^2-1}{p^2} \times \cdots \times \frac{p^m-1}{p^m}$$

同余

若整数$a$和整数$b$除以正整数$m$的余数相等，则称为$a$，$b$模$m$余数相同，则称为$a$，$b$模$m$同余，记为$a \equiv b\pmod m$。

同余满足反身性、对称性、传递性。

• $a \equiv a\pmod m$

• 若$a \equiv b\pmod m$，则$b \equiv a\pmod m$

• 若$a \equiv b\pmod m$，$b \equiv c\pmod m$，则$a \equiv c\pmod m$

翡翠定理

又称贝祖公式，指的是当$ax+by=m$有整数解时，只有$m$是$a$和$b$的最大公约数$d$的倍数。
翡翠等式有解时必然有无穷多个整数解，每组解$x$、$y$都成为翡翠数，可以使用扩展欧几里得算法求得。

扩展欧几里得算法

已知整数$a$、$b$，扩展欧几里得算法可以在求得$a$、$b$的最大公约数的同时，找到整数$x$、$y$（其中一个很可能是负数），使它们满足翡翠等式$ax+by=gcd(a,b)$。
如果$a$是负数，可以把问题转化成$|a|(-x)+by=gcd(|a|,b)$，然后令$x’=(-x)$。

斐波那契数列

$f(1) = 1$

$f(2) = 1$

$f(3) = f(1) + f(2) = f(3-2) + f(3-1)$

$f(n) = f(n-2) + f(n-1)$

卡特兰数

$f(0) = 1$

$f(1) = 1$

$f(n) = f(0) \times f(n-1) + f(1) \times f(n-2) \cdots + f(n) \times f(0)$

应用：长度为n的栈一共有多少种出栈的方法。

二叉树

前序遍历：根左右

中序遍历：左根右

后序遍历：左右根

初赛知识点

渐进时间复杂度

位运算

异或

相同为0，不同为1。

$n^{\wedge}0$不变，$n^{\wedge}1$取反。

补码

源码的绝对值取反加1。

运算顺序

赋值运算符 < 逻辑运算符 < 关系运算符 < 算数运算符

排列组合

全排列

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

全组合

$$
C^m_n= \frac{A^m_n}{A^m_m} = \frac{n \times (n-1) \times (n-2) \times \cdots \times (n-m+1)}{1 \times 2 \times 3 \times 4 \times \cdots \times m} = \frac{n!}{m!(n-m)!}
$$

逆序对

$A[1 \ldots n]$如有$i \lt j$且$A[i] \gt A[j]$则称为逆序对。

模运算

$$(a \times b) \bmod p = (a \bmod p \times b \bmod p) \bmod p$$

$$(a+b) \bmod p = (a \bmod p + b \bmod p) \bmod p$$

$$(a-b) \bmod p = (a \bmod p - b \bmod p) \bmod p$$

$$(a^b \bmod p) = ((a \bmod p) ^ b) \bmod p$$

$$((a+b) \bmod p + c) \bmod p = (a + (b+c) \bmod p) \bmod p$$

$$((a+b) \bmod p \times c) \bmod p = ((a \times c) \bmod p + (b \times c) \bmod p) \bmod p$$

二分查找

mid = (l + r) / 2;等价于mid = l + (r - l) / 2。

第一种写法可能会爆int。

求最小值最大（最大值最小）一般使用二分答案来进行求解。

整数二分

1
2
3
4
5
6
7
8
9

int erfen(int l, int r) {
    int mid;
    while (l <= r) { // 注意二分条件
        mid = (l+r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

实数二分

1
2
3
4
5
6
7
8
9

double erfen(double l, double r) { // dlt = 0.001(精度)
    double mid;
    while (fabs(l-r) > dlt) {
        mid = (l+r) / 2.0;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

数据结构

堆

Min-heap: 父节点的值小于或等于子节点的值。

Max-heap: 父节点的值大于或等于子节点的值。

STL

• upper_bound
  找到第一个大于x的数。

• lower_bound
  找到第一个大于等于x的数。

• greater<int>()
  降序排列。

• less<int>()
  升序排列。

• priority_queue<int, vector<int>, greater<int> > heap;
  优先队列（大根堆）。

• priority_queue<int, vector<int>, less<int> > heap;
  优先队列（小根堆）。

• next_permutation(a, a+n)
  生成a的全排列。

  1 2 3 4 5

  do { for (int i = 0; i < n; i++) printf("%d ", a[i]); printf("\n"); } while (next_permutation(a, a + n);

小技巧

• scanf(" %c", &n)
  其中%c前面加一个空格可以过滤掉一切的空格，回车以及Tab，如果没有的话则不影响。

• 函数有返回值而不返回或者数组下标越界可能会产生各种奇怪的问题，比如C++11能AC但是C++14会RE等等。

• 用memset给int赋值为0x7f即为近似最大值，二进制位为0111 0111 0111 0111。

• 有向无环图的单源点最短路使用BFS算法最佳。

思考

搜索究竟解决的是一个什么问题？

在某一个空间里寻找目标。

空间指的是解空间。

目标指的是目标状态。

• 解空间：如果把一个问题的解抽象成一个数学上的向量，那么包含这个向量的空间，就是解空间。
• 目标状态：用于描述问题或者问题的解的一些量（我是谁？我在哪？）。

(有助于理解动态规划?)

判断N是否是质数，为什么判断到根号n就可以了？

首先，约数是成对出现的。比如24，你找到个约数3，那么一定有个约数8，因为24/3=8。

然后，这对约数必须一个在根号n之前，一个在根号n之后。因为都在根号n之前的话，乘积一定小于n（根号nX根号n=n），同样，都在根号n之后的话，乘积一定大于n。

所以，如果你在根号n之前都找不到约数的话，那么根号n之后就不会有了。