做题方法整合

· · 个人记录

待做：CF2138C1

数论

裴蜀定理

对于不全为 0 的整数 a , b。

对于任意整数 x,y 都满足 \gcd(a , b) \mid ax + by。

存在整数 x , y 使 ax + by = \gcd(a,b)。

应用 1：加若干倍 k 在模 m 意义下取值问题。

$(a + kb)\bmod m$ 的取值为 $a \bmod \gcd(b , m) + k\gcd(b,m)$，$k \in \Z$。 可以把它看成 $\displaystyle \frac{m}{\gcd(b,m)}$ 的塔，每层 $0\sim \gcd(b,m) - 1$。 **例题：** [CF2134B](https://www.luogu.com.cn/article/qgoudnwi)，CF2123G。 ### 因子个数 $d(x)

应用 1：n \le k 时 \max\{d(n)\}。

$k = 10^6$，$\max\{d(n)\} = 240$。 $k = 10^9$，$\max\{d(n)\} = 1344$。 #### 应用 $2$：分解质因数算因子个数。 先根据唯一分解定理分解： $x = \prod p_i^{\beta_i}

则 d(x) = \prod (\beta_i + 1)。

\gcd 相关

应用 1：\gcd 可以视为集合的交，\text{lcm} 可以视为集合的并。

例题： CF2126E。

整除分块

对于正整数 n，\displaystyle \lfloor \frac{n}{i}\rfloor 的可能性最多 2\sqrt n 种。

组合数学

容斥

满足每一个条件的并 是 同时满足奇数个条件 减去 同时满足偶数个条件。

图论

桥

无向图两点间任意一条路径上的桥是两点路径的必经边。

树论

修改邻点/边信息 \to 父节点和子节点分开统计

CF2126F：每个点给子节点连的边用 map 记录信息，父节点单独计算。

HDU7999：树上带修最大值，想到树剖；邻点信息，想到父亲孩子分开统计。两个拼一起就是正确做法了。

树上启发式合并

应用场景：每个点有个颜色，求每个点子树颜色数类似问题。

做法：把自己和轻儿子的信息都并到重儿子里。

复杂度分析：对于每个点，到根节点的轻链个数不超过 \log n，只有遇到轻链它才被计算贡献，所以总复杂度 O(n\log n)。

写法：STL 的 swap 是 O(1) 的，可以不断地把大孩子换到当前点来，然后再合并。

树的直径

求法 1：

随便选一个点 x，找到 dis_{x,i} 最大的点，令 i 为直径的一个端点，再找到 dis_{i,j} 最大的点，j 即为另一个端点。

证明显然，反证法即可。

求法 2：

找到每个点子节点到底部的最大值，给两个最大的子节点的和 +1 取个 \max 即可。

博弈