笔记
数论
基于质因数的最小公倍数求解
采用两两合并的形式，根据最小公倍数的性质可知：$n$ 个数的最小公倍数是这些数中每个数进行质因数分解后，所有的质因数按对应次数累乘的最终结果。
- 预处理：根据题目给的数据范围进行质数打表。本题题目范围是 $1e9$，因此需要计算 $sqrt(1e9)$ 范围内的质数。
- 根据质数表找检查每个数的质因数和其对应的次数：
- 如果一个质因数在不同的数中都有分解出，则次数取高者。
- 需要注意如果遍历完所有表内质数后，该数还有剩余，则它是一个在 $sqrt(1e9)$ 范围外的质数，需要单独记录。
- 基于快速幂求质因数表的乘积和，注意取模。
基于欧几里得算法的最大公约数求解
即辗转相除法，快速求最大公约数。
已知 $a, b$ 两数，求两者最大公约数，用其中大数除以小数，取余数；对于小数和余数，用大数除以小数，取余数……直到余数为 0，此时的除数就是两者的最大公约数。
基于数学方法的回文数判断
对于 int 型的数字串，如果转换为字符串再判断会有频繁的栈开销和较大的常数，因此可以考虑通过提取 + 翻转原数（除10取模，模*10 ，直到中间位）的后半段，并判断翻转后的数字串是否和前半段相等来快速推断。
组合数计算
从 $m$ 个不同元素中不重复、不考虑顺序地选出 $n$ 个的方式总数：
$$C(m, n) = \binom{m}{n} = \frac{m!}{n!(m-n)!}$$
如果需要去重需要在计算前：
std::vector<int> A = {1, 2, 2, 3};
std::set<int> unique_set(A.begin(), A.end()); // 自动去重
std::vector<int> unique_vec(unique_set.begin(), unique_set.end());
前缀和/差分
需要尤其注意边界检查。
等差数列一维差分
已知数组arr，对其进行$k$次操作，每次操作选取左右两个端点，给定一个相同长度的等差数列[s,e,d]表示数列首尾和公差，一一对应加在选取的区间上，求多次操作后的结果。
本质上是两次一维差分，和一维差分相同，不支持边查边改；在每次操作的预处理中和一维差分有所区别，执行以下四步：
arr[l]+=sarr[l+1]+=d-sarr[r+1]-=d+earr[r+2]+=e
二维差分
在遇到二维矩阵+区域覆盖时考虑二维差分，总体思路是对数据进行预处理后进行二维前缀和，得到的就是每个元素的变化值。
给定矩阵$matrix$，进行$k$次操作，每次操作对以$[lx,ly]$和 $[rx,ry]$分别为左上顶点和右下顶点的矩形区域中的每个值加$v$，则进行以下预处理：
pre[lx][ly]+=vpre[lx][ry+1]-=vpre[rx+1][ly]-=vpre[rx+1][ry+1]+=v