题面
给定 \(N\) 个正整数对 \((a_i, b_i)\) 和两个初始为空的集合 \(S, T\)，你可以选择将每个数对的两个元素划分到两个不同的集合中。求
\[\max\operatorname{lcm}(\gcd\limits_{x \in S}x, \gcd\limits_{y \in T}y)
\]
（\(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;
}