基础数论

zzh_2007 · 2023-11-12 18:59:23 · 个人记录

筛质数

1. 埃氏筛 较为常用

2. 线性筛 可用来求一个数的最小的因子

题:NOIP2021报数

乘法逆元

求逆元的三种方法

1. 模数是质数时：费马小定理 较为好写

2. 不是质数时：扩展欧几里得 转化为ax+by=1的形式

3. 线性求逆元 公式: inv[i]=\left \lfloor p/i \right \rfloor\times inv[p\:mod\:i]\:mod\:p \

题:AHOI2005洗牌

扩展欧几里得

板子：NOIP2012 提高组 同余方程

证明：

其实就是gcd(a,b)=gcd(b,a%b)的一个变形 背板子就行

题:青蛙的约会

中国剩余定理

板子 过了

题：P1495

组合数学

较难 常与dp结合

几种求组合数的方法

1. 杨辉三角 n,m较小

   C_{n}^{m} =C_{n-1}^{m} +C_{n-1}^{m-1}

2. 线性递推 n唯一时

   C_{n}^{m}=\frac{n-m+1}{m}* C_{n}^{m-1}

3. 通项公式

4. 质因数分解

5. 卢卡斯定理

   C_{n}^{m}$ $mod\:p$ = $C_{n\:mod\:p}^{m\:mod\:p}* C_{n/p}^{m/p} mod\:p

   一些公式

6. \sum_{i=0}^{b} C_{i}^{m} =C_{b+1}^{m+1}
7. C_{n}^{r} C_{r}^{k} = C_{n}^{k}C_{n-k}^{r-k}
8. \sum_{i=0}^{k} C_{n}^{i} C_{m}^{k-i}=C_{n+m}^{k}
9. \sum_{i=0}^{n}iC_{n}^{i}=n* 2^{n-1}

   ......

   容斥:

   最基本的思想就是 所有方案-不合法的方案=合法方案

   例题：Cheerleaders

   题目中要求网格图的四个边都至少有一个人

   根据容斥的思想 答案即为 第一条边至少有一个人的方案+第二条......-第一条和第二条都至少有一个人-第一条和第三条......以此类推

• 二项式反演

  记 f_n 表示恰好使用 n 个不同元素形成特定结构的方案数，g_n 表示从 n 个不同元素中选出 i \geq 0 个元素形成特定结构的总方案数。

  g_n = \sum_{i = 0}^{n} \binom{n}{i} f_i f_n = \sum_{i = 0}^{n} \binom{n}{i} (-1)^{n-i} g_i

  题目中有这些字眼 "恰好"等 且求"至少" "至多" 的方案 比较好求，我们就可以考虑使用二项式反演

题：

组合数：车的放置\ CQOI2014数三角形

容斥：HAOI2008硬币购物

二项式反演：已经没有什么好害怕的了