[ARC124C] LCM of GCDs 题解

题面

给定 \(N\) 个正整数对 \((a_i, b_i)\) 和两个初始为空的集合 \(S, T\)，你可以选择将每个数对的两个元素划分到两个不同的集合中。求

（\(1 \le N \le 50, 1 \le a_i, b_i \le 10^9\)）。

题解

首先，对于任意正整数 \(x, y\)，有 \(\gcd(x, y) \mid x\)，所以我们设 \(A = a_1, B = b_1\)，因为两个集合等价，故我们钦定 \(A \in S, B \in T\)，所以有 \(\gcd\limits_{x \in S}x \mid A, \gcd\limits_{y \in T}y \mid B\)。

因为有 \(A, B \le 10^9\)，所以 \(A, B\) 的约数个数是很少的，所以我们可以枚举 \(A, B\) 的约数 \(x, y\)，并 \(\mathcal{O}(N)\) 判断其是否可以成为集合的最大公约数，若可行则更新答案。

总复杂度 \(\mathcal{O}(d(A)d(B)N)\)，可以通过本题。

Code

#include <bits/stdc++.h>

typedef long long valueType;
typedef std::vector<valueType> ValueVector;
typedef std::pair<valueType, valueType> ValuePair;
typedef std::vector<ValuePair> PairVector;

valueType lcm(valueType a, valueType b) {
    return a / std::__gcd(a, b) * b;
}

ValueVector divisor(valueType n) {
    ValueVector result;

    for (valueType i = 1; i * i <= n; ++i) {
        if (n % i == 0) {
            result.push_back(i);

            if (i * i != n)
                result.push_back(n / i);
        }
    }

    std::sort(result.begin(), result.end());

    return result;
}

bool check(valueType a, valueType b, PairVector const &data) {
    return std::all_of(data.begin(), data.end(), [a, b](ValuePair const &iter) {
        return (iter.first % a == 0 && iter.second % b == 0) || (iter.second % a == 0 && iter.first % b == 0);
    });
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    valueType N;

    std::cin >> N;

    PairVector data(N);

    for (auto &iter: data)
        std::cin >> iter.first >> iter.second;

    ValueVector const A = divisor(data[0].first), B = divisor(data[0].second);

    valueType ans = 0;

    for (auto const &a: A)
        for (auto const &b: B)
            if (check(a, b, data))
                ans = std::max(ans, lcm(a, b));

    std::cout << ans << std::endl;

    return 0;
}