「划水」CF1322C Instant Noodles

看到「和」与 $\gcd$ ，就会有一个比较 trivial 的想法，即 $$ \begin{aligned} &\gcd(x_1,x_2)=\gcd(x_1,x_2-x_1)\\ \to&\gcd(x_1,x_2,x_3,\cdots,x_k)=\gcd(x_1,x_2,x_3\cdots,x_k-x_1-x_2-x_3-\ldots) \end{aligned} $$ 这一点可以用 $\gcd$ 的传(结)递(合)性(律)来证明。 然后一个比较直接的想法就是，考虑左边的点会怎么产生贡献。不难发现如果两个左部的点 $x,y$ 满足 $N(x)\cap N(y)=\emptyset$ ，那么同时选这两个的所有贡献都可以忽略。但是问题就出在 $\mathrm{card}\left( N(x)\cap N(y)\right)>0$ 的情况。这个时候很难去除交集的贡献。 但是如果将目光放到右部，就会发现关于 $\gcd$ 的那个式子依旧满足，但是此时要换成如果与两个右部点 $x',y'$ 分别连通的左部点集合 $M(x'),M(y')$ 存在交集，那么就可以直接去除掉这一部分，因为这部分的 gcd 一定是多个 $c_i$ 的和的形式。 发现从右部入手和从左部入手本质上没有什么不同，但不同就不同在有关右部的集合运算可以方便加减以及计算贡献，但是左部不行。因为本质上左部提供关系，右部提供权值。所以从右部考虑方便是显然的结论。 但是需要注意一个小点。$\gcd(x,x)=x$，但是按照上述方式会算成 $\gcd(x,x)=0$ 。所以需要 hash 一下去判一下 $M(x')=M(y')$ 的 $(x',y')$，比较方便的方式就是直接合并两者。 模数 `P` 可以取 $10^9+7$，`Base` 可以取 `131`。事实证明没有卡单哈希。如果 T 掉了，可以考虑将 `iostream` 换成 `cstdio`。