ABC20D
题意：
给定 \(n\le 10^9,k\le 100\) ，求 \(\sum\limits_{i=1}^n \text{lcm}(i,k)\)，对 \(10^9+7\) 取模。
做法：
\(\sum\limits_{i=1}^n \text{lcm}(i,k)=\sum\limits_{i=1}^n \dfrac{ik}{\gcd(i,k)}=k\sum\limits_{d\mid k}\dfrac{1}{d}\sum\limits_{i=1}^n [\gcd(i,k)=d]i=k\sum\limits_{d\mid k}\sum\limits_{i=1}^{[\frac{n}{d}]} [\gcd(i,\dfrac{k}{d})=1]i\)
\(d\mid k\) 的 \(d\) 的个数是 \(O(\sqrt k)\) 的，下面考虑快速求\(1\) 到 \(n\) 和 \(\dfrac{k}{d}\) 互素的数的和。
枚举 \(\dfrac{k}{d}\) 的因数，进行容斥即可，复杂度 \(O(\sqrt k)\)。
于是总复杂度 \(O(k)\)。
ABC133F
题意：
有一个 \(n\) 个节点的树，每条边有颜色、边权。
您需要处理 \(q\) 个询问，每个询问给出 \(x_i,y_i,u_i,v_i\)，您需要求出假定所有颜色为 \(x_i\) 的边边权全部变成 \(y_i\) 后，\(u_i\) 和 \(v_i\) 之间的距离。询问之间互相独立。
\(1\le n,q\le 10^5\)，题目中颜色均 \(\le n-1\)，所有边权均 \(\le 10^4\).
做法：
题解区全部都做复杂了。
定义 \(d_x\) 表示 \(1\to x\) 的路径长度。考虑 \(dis(x,y)=d_x+d_y-2d_{\text{lca(x,y)}}\)。
如果不考虑边权变化直接一遍 \(dfs\) 即可。
询问离线下来，在点 \(u,v\) 处都打一个 \((x,y,id)\) 的标记，在 \(\text{lca}\) 处打一个 \((x,y,-id)\) 的标记。然后 \(dfs\) 的时候记录 \(1\) 到当前节点：每种颜色出现次数，每种颜色的边权和，然后在每个点对对应答案进行修改即可。
复杂度（假设 \(n,q\) 同阶）为：\(O(L(n)+n)\)，\(L(n)\) 表示 \(n\) 次求 \(\text{lca}\) 的复杂度，一般为 \(n\log n\)。非常优秀，而且代码比题解区短多了。
ABC132F
题意：
求有多少长度为 \(n\) 的正整数序列，满足任意两个相邻的数的乘积不超过 \(m\)，答案对 \(10^9+7\) 取模。（注意 \((n,m)\) 对应原题 \((K,N)\)，为了方便写作）
\(1\le n\le 100,1\le m\le 10^9\) .
做法：
下面除法均下取整。
这显然 \(\texttt{dp}\)，或者说是递推。看到除法和 \(10^9\)的数据范围，很显然想到用整除分块优化 \(\texttt{dp}\)。
因为 \(\texttt{dp}\) 肯定要和前一项有关，那这一项和前一项有关的方法只能用 \(m\) 去除。所以我把状态设成了 \(f_{i,j}\) 表示做到第 \(i\) 项，\(m/a_i=j\) 的方案数。
我们先把所有可能的 \(m/a_i\) 用整除分块筛出来，用一个数组 \(b\) 存储。定义 \(c\) 满足 \(c_{b_j}=j\)。这时候状态就要改一下了，变成 \(f_{i,j}\) 表示做到第 \(i\) 项，\(m/a_i=b_j\) 的方案数。
然后就考虑 \(\texttt{dp}\) 方程。设 \(m/a_i=x,m/a_{i-1}=y\)。
则 \(xy\ge\frac{m}{a_i}\times \frac{m}{a_{i-1}}=\frac{m^2}{a_i\times a_{i-1}}\ge m\)。
所以 \(y\ge m/x\)。
这时候枚举范围就是 \(b\) 中在 \(m/x\) 到 \(n\) 之间的数。由于整除分块的时候是逆序的，所以枚举范围是\(b_{1,\dots,c_{m/x}}\)。
\(\texttt{dp}\) 方程为：\(f_{i,j}=f_{1,j}\times\sum\limits_{k=1}^{c_{m/x}} f_{i-1,k}\)，初始化 \(f_{1,i}\) 为满足 \(m/x=i\) 的 \(x\) 的个数，在整除分块时一起筛出来。
但这个时候复杂度是 \(O(nm)\) 的。前缀和优化即可，最终复杂度 \(O(n\sqrt m)\)。