1322C Instant Noodles

· · 题解

题意

给定一个二分图，左右各 n 个点，右侧点有点权 c_i，对于非空左侧点集 S，f(S) 为右侧点中至少与 S 中一个点相连的点的点权和，求所有 f(S) 的 \gcd。

其中 n\le 5\times 10^5，c_i\le 10^{12}。

解法

考虑 \gcd 的一些性质，先删去和合并一些点。

对于右侧点 i，设 G(i) 为其所连接的左侧点集，则：

  1. 若 |G(i)|=0，i 不会被算到任何 f(S) 中，故舍弃；

  2. 若 G(i)=G(j)，则 i 和 j 在任何 f(S) 中要么都被算上，要么都不算，故合并 i,j，新点权为 c_i+c_j；

在这样的操作后，我们得到了一个新的右点集，其中 T(i)>0 且 T(i)\neq T(j)。

对于新的两点 i,j，每次的 f 必然是 (c_i,c_j),(c_i+c_j,c_i),(c_i+c_j,c_j),(c_i,c_j,c_i+c_j) 中的一个，其值均为 (c_i,c_j)。

此时答案为所有点权值的 \gcd。