这个笔记想写得稍微详细一点，部分内容来自我自己之前的博客: OI 里的数学内容整理（提高组）。 其中一些公式是 AI 从 PPT 上识别的，格式混乱，还请谅解。 整数分解与筛法 欧几里得算法 用于求解两个数的最大公因数。 $\gcd(a,b)=\gcd(b,a\bmod b)$。 int gcd(int a,int b){ return b==0?…

图匹配 二分图匹配 判定 静态：黑白染色。 动态：分层并查集。并查集可以维护的可以是点的连接关系，也可以是关系的连接方式。连接两个点，我们可以改为连接这两个点的逻辑关系，黑-白，白-黑。如果有一天同一个点的黑白被连在了一起，则这就不是一个二分图。 分层并查集经典例题：P2024 [NOI2001] 食物链。 最大匹配：匈牙利算法 模版：P3386 …

基础数据结构（前缀和/差分/树状数组/线段树） 前缀和与差分 多维前缀和 多维前缀和可以通过一维一维处理的方式，将复杂度控制在可控范围。 例如二维前缀和求法： 1. $sum_{i,j}=a_{i,j}$ 2. $sum_{i,j}+=sum_{i-1,j}$ 3. $sum_{i,j}+=sum_{i,j-1}$ 例题：NC225630 智乃酱的…