数论与几何

这部分知识点比较考验数学功底和思维。

水塘抽样（Reservoir Sampling）是一系列的随机算法，其目的在于从包含n个项目的集合S中选取k个样本，其中n为一很大或未知的数量，尤其适用于不能把所有n个项目都存放到内存的情况。水塘抽样由于空间小，时间复杂度低，可以用于大数据流中的随机抽样问题。

遍历集合，当我们第 i 次遇到值为 target 的元素时，随机选择区间 $[0,i)$ 内的一个整数，如果其等于 0，则将返回值置为该元素的下标，否则返回值不变。设 nums 中有 k 个值为 target 的元素，该算法会保证这 k 个元素的下标成为最终返回值的概率均为 $1/k$，证明如下：
$\begin{aligned} &P(第\ i\ 次遇到值为\ \textit{target}\ \ 的元素的下标成为最终返回值)\
=&P(第\ i\ 次随机选择的值= 0) \times P(第\ i+1\ 次随机选择的值\ne 0) \times \cdots \times P(第\ k\ 次随机选择的值\ne 0)\
=&\dfrac{1}{i} \times (1-\dfrac{1}{i+1}) \times \cdots \times (1-\dfrac{1}{k})\
=&\dfrac{1}{i} \times \dfrac{i}{i+1} \times \cdots \times \dfrac{k-1}{k}\
=&\dfrac{1}{k} \end{aligned}$

num = random.choice(list())：在list中随机返回一个num
num = random.randrange(start, end, step)：指定排列中随机返回一个num
求a和b的最大公约数和最小公倍数为：math.gcd(a, b) 和 a * b / gcd(a, b)
给定一个整数：不同的质因子数量$\omega$，所有的质因子数量$\Omega$

高中基础

从n个不同的元素中取出m个元素的排列数：$A(n,m)=A^m_n=n(n-1)(n-2)…(n-m+1)=\frac{n!}{(n-m)!}$
从n个不同的元素中取出m个元素的组合数：$C(n,m)=C(n,n-m)=\frac{A^m_n}{m!}=\frac{n!}{m!(n-m)!}$
规定$0!=1$。python中对应函数分别为itertools.permutations(list, m);itertools.combinations(list, m)。math.perm(n, k);math.comb(n, k)从n个项目中选择k个项目(不重复且无顺序)的排列数和组合数。
等差数列通项：$a_n=a_1+(n-1)d=a_m+(n-m)d$，求和公式：$S_n=na_1+\frac{n(n-1)}{2}d=\frac{n(a_1+a_n)}{2}$
等比数列通项：$a_n=a_1q^{n-1}=a_mq^{n-m}$，求和公式：$S_n=\frac{a_1(1-q^n)}{1-q}=\frac{a_1-a_nq}{1-q}$

力扣指南

数论与几何
题目	技巧	难度
✅172. 阶乘后的零	因子5的数量必小于2的数量，循环计算n除5的结果数	🌟🌟
✅阶乘函数后 K 个零	末尾0为k+1的数量的左边界 - 末尾0为k个的数量的左边界 = 末尾0为k的数量	🌟🌟🌟
✅204. 计数质数	埃氏筛：质数的倍数肯定是合数	🌟🌟
✅50. Pow(x, n)	10的二进制为1010，即x^10=x^2*x^8	🌟🌟
✅372. 超级次方	正序逆序计算均可	🌟🌟
✅398. 随机数索引	水塘抽样	🌟🌟
✅382. 链表随机节点	水塘抽样	🌟🌟