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;
}