题解：CF1322C Instant Noodles

· · 题解

思路还是很简单的。

对于右侧的两个点 x,y，其向左所连的点集分别为 S_x 和 S_y。

分别考虑一下情况：

若 S_x\cap S_y=\varnothing，结果就是 \gcd(c_x,c_y)。

若 S_x\cap S_y\ne\varnothing，此时若 S_x=S_y，那么就相当于两个一样的集合，不用管它，若不然则答案无非就是 \gcd(c_x+c_y,c_y),\gcd(c_x,c_x+c_y),\gcd(c_x,c_y,c_x+c_y) 这几种，根据辗转相除法，显然这些的结果都是 \gcd(c_x,c_y)。

那么我们用哈希维护一下集合就行了，这里我用的是 map。

注意多测清空，要开 long long。

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
#define int long long
int n, m, ans;
int c[N];
set <int> g[N];
map < set <int>, int > p;
void solve() {
    ans = 0, p.clear();
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> c[i];
    for (int i = 1; i <= n; i++) g[i].clear();
    for (int i = 0, u, v; i < m; i++)
        cin >> u >> v, g[v].insert(u);
    for (int i = 1; i <= n; i++)
        if (!g[i].empty()) p[g[i]] += c[i];
    for (auto i : p) ans = __gcd(ans, i.second);
    cout << ans << '\n';
}
signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T; cin >> T; while (T--) solve();
}