你好，我是 zbl2012 👋

质数筛也是数论中非常重要的一个部分。 根号筛 这个是很多人第一个学的筛法，也是最简单的筛法。 做法很简单，就是枚举 2 到 n-1 里所有的数，如果当前数可以被 n 整除，那么 n 显然就是一个和数。直到跑完循环也没返回，就说明 n 是一个指数。当然，n<2 要特判，n=2 也要特判。这样做每次判断一个数的时间复杂度是 On，判断 n 个数的时间复杂度是 On^2。太慢了，要优化。 ...

从 1,2,3,...,n 中选择 m 个数的方案数，记为 \dbinom{n}{m}，也可记为 C^mn。读作 “n 取 m”。\dbinom{n}{m}=\frac{n!}{m!n-m!} On^2 引理：在杨辉三角中的第 n 行 m 列等于 \dbinom{n}{m}。 根据这个引理，我们可以用构造杨辉三角的形式构造组合数。 杨辉三角的构造很简单，就是当前位等于上面的加左上的，也就...

逆元的诞生是源于除法没有同余定理。 逆元的定义：在模意义下，一个数 a 除以 b，等于乘 b 的逆元。 首先我们要知道什么是同余定理。其实就是针对取模的运算的基本原理： 当 a\equiv b\pmod m,c\equiv d\pmod m,m>0 时： a+c\equiv b+d\pmod m\\a-c\equiv b-d\pmod m\\ac\equiv bd\pmod m ...

快速幂是很多数学题的最基本的东西，是一种可以在 O\log n 的复杂度求解 a^n 的问题的算法。 一般来说，求解 a^n 的问题要循环 n 次，每次乘 a，时间复杂度 On。 但是快速幂用到了一个性质：任何一个正整数都可以写成几个 2 的次幂的和，其实就是可以转换成二进制。 所以可以将 a^n 转换成： n=2^{x1}+2^{x2}+2^{x3}+...+2^{xt},t\le\...

计数最基础的东西。 首先我们要知道什么是计数。 集合 A 的计数用 |A| 表示，计数的严格表示就是： |A|=\sum{a\in A}1 其实就是集合 A 中的元素个数。 容斥原理就是它的字面意思，容表示加，斥表示减，所以容斥原理就是加加减减。我们都学过，如果两个没有交集的集合 A 和 B 取并集的计数就是直接讲两个集合的计数相加，也就是 |A \cup B|=|A|+|B|,A\...