Codeforces 1322C - Instant Noodles(数学)

题意

给出一个二分图, 两边各 n 个点, 共 m 条边, n, m ≤ 5e5. 右边的点具有权值 \(c_i\), 对于一个只包含左边的点的点集 S, 定义 N(S) 为所有与这个点集相邻的右边的点的点集, f(S) 为这些点的权值和. 问所有可能的 f(S) 的最大公因数.

思路

考虑若干个右边的点, 如果它们对应的左边的点是一致的, 说明它们在 N(S) 中一定是同时出现, 所以把它们缩成一个点, 新权值为原来的权值和. 缩点后在再除去那些度数为 0 的点, 下面证明答案就是剩下的点的权值的 gcd. 后面提到的 \(c_i\) 是已经过上述处理的.

设此时得到的答案为 g, 答案真值为 G. 显然 g 整除所有 f(S), 得到 \(g | G\). 设 \(G = k × g\). 令所有 \(c_i\) 都除以 \(g\). 假设 \(k > 1\), 则存在一个 \(c_j\), 使得 \(k \nmid c_j\), 设所有不与该点的相邻的点构成集合 S', 左边的点全集为 U, 则 N(S') 为仅不包含点 j 的右边点集合, 因为如果还有其他点也不被包含, 这与已缩点是矛盾的. 因为 \(k | f(U), k \nmid c_j\), 所以 \(k \nmid f(U-S')\), 得出矛盾. 所以 \(k = 1, g = G\).

代码

#include <bits/stdc++.h>

using namespace std;

#define ll long long

#define inc(i, l, r) for (int i = l; i <= r; i++)

const int maxn = 5e5 + 5;

int t, n, m, u, v;

ll c[maxn];

vector<int> g[maxn];

int main() {

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    cin >> t;

    while (t--) {

        cin >> n >> m;

        inc(i, 0, n - 1) vector<int>().swap(g[i]);

        inc(i, 0, n - 1) cin >> c[i];

        inc(i, 0, m - 1) {

            cin >> u >> v;

            u--, v--;

            g[v].push_back(u);

        }

        inc(i, 0, n - 1) sort(g[i].begin(), g[i].end());

        vector<int> id(n);

        iota(id.begin(), id.end(), 0);

        sort(id.begin(), id.end(), [&](int a, int b) { return g[a] < g[b]; });

        ll res = 0;

        for (int i = 0, j; i < n; i = j) {

            ll sum = 0;

            j = i;

            while (j < n && g[id[i]] == g[id[j]]) {

                sum += c[id[j]];

                j++;

            }

            if (g[id[i]].size()) res = __gcd(res, sum);

        }

        cout << res << "\n";

    }

}

巴特西

Codeforces 1322C - Instant Noodles(数学)

题意

思路

代码

最新文章

热门文章