质数
- 质数判定 试除法 $O(\sqrt{n})$
- 筛法 线性筛法 $O(N)$ 埃氏筛法 $O(nloglogn)$
两个重要复杂度分析
- $\frac{1}{1} + \frac{1}{2} + \frac{1}{3} + … + \frac{1}{n} \approx logn$ n为自然数
$\frac{1}{2} + \frac{1}{3} + \frac{1}{5} + … + \frac{1}{n} \approx loglogn $ 底数全为质数 - 一个结论：如果一个数为合数，那么它至少存在质因子$x <= \sqrt{n}$。 这条结论可以判断出连续一段很大的数中存在多少质数 假如要求出l ~ r之间的数中存在多少质数，既可以先求出$\sqrt{r}$中的所有质因子，再用这些质因子去筛存在l ~ r之间的所有质因子的倍数，时间复杂的为$(r - l) loglogr$
分解质因数
-
试除法 $O(\sqrt{n})$ 优化 $O(\sqrt{n} / logn)$ 方法先预处理出 $1 — \sqrt{n}$ 中所有的质因子再用试除法来做（一般用在只卡时那么一点点时长上面）
-
阶乘分解 $O(n)$ 先预处理出$1 - n$中所有的质因子,再依次计算每个质因子有多少个，质因子大概有$\frac{n}{logn}$个，每个最坏处理$logn$次因此总体是线性的$O(N)$
约数
- 试除法$O(\sqrt{n})$ 优化：$O(\sqrt{n} / logn)$方法先预处理出 $1 - \sqrt{n}$ 中所有的质因子并且保存下来，再用dfs进行组合所有约数，（比较常用）因为一个数的约数很少。上界为$2\sqrt{n}$个
- 求$1 - n$所有数的正约数 - 倍数法 : 依次枚举每个数，再枚举每个数的倍数，$O(nlogn)$ 上面两个时间分析是相当的有用
妙哉 妙哉 - 求$k mod 1 + k mod 2 + … + k mod n = ? 1 =< n, k <= 1e9 $暴力显然超时，
欧拉函数
- 根据定义$O(\sqrt{n})$
- 求$1 - n$的欧拉函数 用线性筛$O(N)$
- 自此线性筛法不但可以筛质数也可以筛欧拉函数还可以筛每个数的最小质因子，还有许多可以筛的俗称万能筛，知道筛其他东西的小伙伴记得@我一下，分享分享$^-^$
同余
- 基本性质（常用）
- 定义：若正整数a和正整数b除以正整数m的余数相等，则称a,b模m同余
- 性质1：若a1 同余 b1(mod m), a2 同余 b2 (mod m) 则 a1 + a2 同余 b1 + b2, a1 * a2 同余 b1 * b2
- 性质2：若a 同余 b(mod m) 对于任意的整数 c 有 a + c 同余 b + c a * c 同余 b * c
- Sundae同学的同余笔记
取模
- (a + b) % p = a % p + b % p
- (a - b) % p = a % p - b % p
- (a * b) % p = a % p * b * p
- (a ^ b) % p = (a % p) ^ b % p
扩展欧几里得算法
- 贝祖定理 ： 若a, b是整数 ，d = gcd(a, b) ,对于任意的整数x, y, ax + by = m ，m一定是d的倍数（特别的，如果a,b是整数一定存在整数x, y使得ax + by = gcd(a, b）。
我们不妨用欧几里得算法来计算x,y已知边界条件成立的时候x = 1, y = 0, 反推出前面的x, y。
- 当计算gcd(a, b)时有 ax1 + by1 = d, 而在进行下一步的时候 又有 bx2 + (a % b)y2 = d, 又a % b = a - a/b * a,因此等式化简为ax1 + by1 = ay2 + (x2 - a/b) b 因此x1 = y2, y1 = x2 - a / b * y2
void exgcd(int a, int b, int &x, int &y)
{
if(!b)
{
x = 1, y = 0;
return ;
}
exgcd(b, a % b, x, y);
int temp = x;
x = y;
y = temp - a / b * y;
}
上式求出的只是x, y的一个特解，假设通解为x + s1, y - s2代入等式有 a(x + s1) + b(y - s2) = d ，
化简得$as1 = bs2 即\frac{a}{b} = \frac{s2}{s1}$ 为了让s1 和 s2 尽可能的小，可以让分钟分母处于一个尽可能大的数那就是他们的最大公约数因此s1,s2的最小取值就是 b/d 和 a/d
同理扩展欧几里得也可以求ax + by = c的解 或者同余式ax 同余 c(mod m)的解
用扩展欧几里得算法求解最小正整数解的前提必须模数是正数
两个定理
- 费马小定理：若p是质数，那么对于任意的整数a有 a^(p - 1) 同余 1 (mod p)
- 欧拉定理 若a, p互质则a^n 同余 1 (mod p) n = p的欧拉函数 推论如果a^k 同余 1 mod(p) 则a, p必然互质，并且k一定是n的约数。
组合计数
- 性质C(n, m) = C(n - 1, m) + C(n - 1, m - 1)
- C(n + 1, 1) + C(n + 2, 2) + … + C(n + m, m) = C(n + 1, n) + C(n + 2, n) + … + C(n + m, n) = C(n + 1, n + 1) + C(n + 1, n) + C(n + 2, n) + … + C(n + m, n) - 1 = C(n + m + 1, n + 1) - 1;
- 根据组合数的性质可用递推法用$O(N^2)$求出 0 =<x, y <= n的所以组合数
- 求C(n, m)mod p的值 如果p是质数并且 p > n 的话可用n! / (m! * (n-m)!)来求 除法用费马小定理求解逆元来求解，时间复杂度为$O(N)$ 如果p不是一个质数的话，由于取模不能计算除法，因此我们求出n以内的所以质数在计算阶乘分解求出每个质因子的个数，最后用快速幂求解时间为$O(NlogN)$
- 如果n， m特别大但是p很小的话就可以用lucas定理来求解， 前提是p为质数 时间为$O(logp + p * loga)$
- 最后一种就是求解C(a, b)的高精度 最快的做法就是先做阶乘分解求质因子再把每个质因子相乘，尽量用数组维护比较快，如果时间很极限的话建议用long long 存储并且压9位，这个是我目前已知最快的方法，有更快的欢迎call我。
- 求解 x1 + x2 + … + xk = n的个数(xi > 0) 可用隔板法来做从n - 1个空位中选择k - 1个空位 C(n - 1, k - 1)
- 求解 l <= a1 <= a2 <= a3 <= … <= ak <= r 求方案数
- 法一： 设x1 = a1 , xi = ai - ai-1 (i >= 2) 上式等价于 l <= x1 + x2 + … + xk <= r (xi >= 0), 设yi = xi + 1 上式等价于 l + k <= y1 + y2 + … + yk <= k + r 由于yi之间只存在相对值所以上式等价于 0 < y1 + y2 + … + yk <= r - l + k 这里可用隔板法来做，这么是不等式因此多用一个隔板答案就是C(r - l + k, k)
- 法二：设xi = ai + i 原式等价于 0 < x1 < x2 < … < xk <= r - l + k 等价于从r - l + k中选k个数
Catalan
分析一道题是不是Catalan的两种方法：
- 从递推式的角度来看，如果如果f[n] = f[1] * f[n - 1] + f[2] * f[n - 2] + … + f[n - 1] * f[1] 的话就是卡特兰数, 列如求二叉树的个数
- 挖掘一种性质：任意前缀中，某种东西一定不能少于等于另一种东西。
- 听一位同学说还有第2.5中具体参考 百度百科 OIWK
容斥原理
- 这种题一般就是对一种性质的求解，给出n个条件，求至少满足其中一个条件的的方案数，就可以用容斥原理求解。
- 答案：S1 - S2 + S3 … Si表示满足i个条件的集合，这种题一般时间复杂度就是$O(2^n)$中常用位运算求解
- 复杂一点的就是求解一种多重集组合数问题
