专栏文章

做题方法整合

BBrotherCallIllenials
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio37149
此快照首次捕获于
2025/12/02 12:37
3 个月前
此快照最后确认于
2025/12/02 12:37
3 个月前
查看原文
待做：CF2138C1

数论

裴蜀定理

对于不全为 00 的整数 a,ba , b。
对于任意整数 x,yx,y 都满足 gcd⁡(a,b)∣ax+by\gcd(a , b) \mid ax + by。
存在整数 x,yx , y 使 ax+by=gcd⁡(a,b)ax + by = \gcd(a,b)。

应用 11：加若干倍 kk 在模 mm 意义下取值问题。

a,b,ma,b,m 为常量，k∈Zk \in \Z。
(a+kb) mod m(a + kb)\bmod m 的取值为 a mod gcd⁡(b,m)+kgcd⁡(b,m)a \bmod \gcd(b , m) + k\gcd(b,m)，k∈Zk \in \Z。
可以把它看成 mgcd⁡(b,m)\displaystyle \frac{m}{\gcd(b,m)} 的塔，每层 0∼gcd⁡(b,m)−10\sim \gcd(b,m) - 1。
例题： CF2134B，CF2123G。

因子个数 d(x)d(x)

应用 11：n≤kn \le k 时 max⁡{d(n)}\max\{d(n)\}。

k=105k = 10^5，max⁡{d(n)}=128\max\{d(n)\} = 128。
k=106k = 10^6，max⁡{d(n)}=240\max\{d(n)\} = 240。
k=109k = 10^9，max⁡{d(n)}=1344\max\{d(n)\} = 1344。

应用 22：分解质因数算因子个数。

先根据唯一分解定理分解：
x=∏piβix = \prod p_i^{\beta_i}
则 d(x)=∏(βi+1)d(x) = \prod (\beta_i + 1)。

gcd⁡\gcd 相关

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

例题： CF2126E。

整除分块

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

组合数学

容斥

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

图论

桥

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

树论

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

CF2126F：每个点给子节点连的边用 map 记录信息，父节点单独计算。
HDU7999：树上带修最大值，想到树剖；邻点信息，想到父亲孩子分开统计。两个拼一起就是正确做法了。

树上启发式合并

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

做法：把自己和轻儿子的信息都并到重儿子里。
复杂度分析：对于每个点，到根节点的轻链个数不超过 log⁡n\log n，只有遇到轻链它才被计算贡献，所以总复杂度 O(nlog⁡n)O(n\log n)。
写法：STL 的 swap 是 O(1)O(1) 的，可以不断地把大孩子换到当前点来，然后再合并。

树的直径

求法 11：

随便选一个点 xx，找到 disx,idis_{x,i} 最大的点，令 ii 为直径的一个端点，再找到 disi,jdis_{i,j} 最大的点，jj 即为另一个端点。
证明显然，反证法即可。

求法 22：

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

博弈

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...