CF1322C Instant Noodles 题解

题意：

有$t$组测试数据。

给出一张点数为$2N$的二分图，其中右侧的第$i$个点有点权为$c_i$。

令$S$表示左侧点的一个非空点集，设$f(S)$表示右侧点中至少与$S$中一个点相连的点的点权和。

请你求出，对于所有非空集合$S$，$f(S)$的$\gcd$为多少。

$1 \leq t,\sum n,\sum m \leq 5\times 10^5$，$1 \leq c_i \leq 10^{12}$。

输入格式：

The first line contains a single integer $t$($1 \leq t \leq 500\,000$) — the number of test cases in the given test set. Test case descriptions follow.

The first line of each case description contains two integers $n$ and $m$ ($1~\leq~n,~m~\leq~500\,000$) — the number of vertices in either half of the graph, and the number of edges respectively.

The second line contains$n$integers $c_i$($1 \leq c_i \leq 10^{12}$) . The$i$-th number describes the integer in the vertex$i$of the right half of the graph.

Each of the following$m$lines contains a pair of integers $u_i$ and $v_i$($1 \leq u_i, v_i \leq n$), describing an edge between the vertex $u_i$ of the left half and the vertex $v_i$ of the right half. It is guaranteed that the graph does not contain multiple edges.

Test case descriptions are separated with empty lines. The total value of$n$across all test cases does not exceed $500\,000$ , and the total value of$m$across all test cases does not exceed $500\,000$ as well.

输出格式：

For each test case print a single integer — the required greatest common divisor.

众所周知，$\gcd(a,b) = \gcd(a+b,b)$ 。

设 $i,j$ 为右侧的两个点，$S_i,S_j$ 为他们分别对应的左侧点集合。

若 $S_i \cap S_j = \varnothing$ ，直接求 $\gcd(c_i,c_j)$
若 $S_i = S_j$ ，则可以直接将 $c_i,c_j$ 合并。
若 $S_i \cap S_j \ne \varnothing$ ，

对于这种情况，我们求的是 $\gcd(c_i,c_i+c_j)$ 或 $\gcd(c_j,c_i+c_j)$ 或 $\gcd(c_i,c_j,c_i+c_j)$ 。

结果发现这玩意好像就是 $\gcd(c_i,c_j)$ 捏。

时间复杂度 $\mathcal{O}(n \log c_i)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(5e5+15))

int n,m,c[N]; set<int> g[N]; map<set<int>, int> mp;
int gcd(int a,int b) { return b == 0 ? a : gcd(b, a%b); }
void work()
{
    mp.clear(); cin >> n >> m; int res = 0;
    for(int i=1; i<=n; i++){ cin >> c[i]; g[i].clear(); }
    for(int i=1,u,v; i<=m; i++) { cin >> u >> v; g[v].insert(u); }
    for(int i=1; i<=n; i++) if(!g[i].empty()) mp[g[i]] += c[i];
    for(auto i : mp) if(res) res = gcd(res, i.second); else res = i.second;
    cout << res << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int _Q = 1; cin >> _Q; while(_Q--) work();
    return 0;
}