「划水」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。