树状数组

堪堪能接受的一场。前两题一个半小时左右做完，后两题实在没什么思路，打完所有可能的暴力之后跑路了。

他们告诉我题目名称可以从上到下连起来读。

一句话题解

A – （种）菜

可以发现，假若同时有 $\newcommand{\bigO}{\operatorname{O}}a_i,a_{i+1}$ 和 $a_{i+1},a_{i+2}$ 都可合并，则取 $a_i, a_{i+2}$ 中任意一个合并之后，质因数集合总是变为原来的超集，另外一项仍可合并。

故而可以贪心合并所有合法的邻项，最终检查是否仅剩一项即可。注意到 $[1,700]$ 仅含 $125$ 个质因数，故可以用 std::bitset 保存每一项的质因子集合。复杂度 $O(\frac{128n}{\omega})$。赛时竟然还开了数组保存每个质因子的实际指数！ （更多…）