CF623B
考虑枚举 \(\gcd=d\)，我们先假设没有 \(a\) 操作，所有数都需要 \(b\) 操作来实现。
那么，形如 \(kd\pm 1\) 的数需要代价为 \(b\)，\(kd\) 的数无需代价，然而可能存在没法通过 \(b\) 操作被 \(d\) 整除的数。
若没有上述数呢，我们现在加入 \(a\) 操作，这是一个最大子段和问题，求出一个子段使得省去代价最多。
如果有上述数，那么必存在 \([l,r]\) 是必选的，那么我们左右找省去代价最多的前后缀即可。
然而我们还要枚举 \(\gcd\)，观察到 \(A_1,A_n\) 有一个必选，所以 \(d\) 很少。于是我们分解质因数出来即可。
CF965E
先把字典树建出，考虑从叶子节点开始往上推。当一个节点合并其儿子节点时：
若该节点没有结尾字符串，可以把儿子中最长的字符串改成这个点结尾的字符串。
那么我们启发式合并即可。
CF653E
如果有解那么去掉 \(1\) 后连通块个数不超过 \(k\)，并且 \(1\) 到这些连通块都有边。
我们用 bfs 找连通块，同时维护一个 set，代表还没去过的点，如果当前到 \(u\)，那么就在 set 里找 \(v\)。
因为只有 \(m\) 条边被删去，所以 \(u\to v\) 最多匹配失败 \(m\) 次，复杂度是 \(O((n+m)\log n)\)。
CF1139D
这是个经典的期望模型，不妨设 \(f_i\) 表示 \(\gcd =i\) 时到 \(1\) 要多少步，\(f_1=0\)。
我们现在看 \(f_y\) 怎么转移到 \(f_x\)，一定满足 \(y|x\)，枚举 \(x\) 下一位是什么，
可以列出 \(f_x=1+\dfrac{1}{m}\sum_{i=1}^m f_{gcd(x,i)}\)，除去 \(\gcd(x,i)=x\) 的情况，\(\dfrac{m-(m/x)}{m}f_x=1+\dfrac{1}{m}\sum_{i \not |x} f_{gcd(x,i)}\)
\(f_x=\dfrac{m+\sum_{i \not |x} f_{gcd(x,i)}}{m-(m/x)}\)，枚举 \(\gcd\)，我们即求有多少个 \(i\in[1,m]\) 使得 \(\gcd(x,i)=y\)。
即数多少个 \(i\in[i,m/y]\)，使得 \(\gcd(x/y,i)=1\)。
设 \(n=m/y\)，\(k=x/y\)，考虑莫反，即求 \(\sum_{i=1}^n\sum_{d|i,k}\mu(d)=\sum_{d|k}\mu(d)\cdot n/d\).
我们可以预处理约数，总的复杂度约为 \(O(n\sqrt n)\)。
CF1088E
我们观察到，如果 \(x_i=x_j\)，那么 \(i,j\) 的邻居指定相同（包括本身）。
所以我们发现，邻居相同的，我们可以直接构造他们为相同的权值。
那么，我们把所有邻居相同的缩点出来，形成一张新图，那么图上相邻的两点权值不同。
所以有度数 \(\ge 3\) 的点肯定无解，有环肯定无解，所以最后就是一个链了，顺序染色即可。
可以用哈希来判断邻居集合。