蓝桥杯真题 - 公因数匹配 - 题解

题目链接：https://www.lanqiao.cn/problems/3525/learning/

个人评价：难度 2 星（满星：5）
前置知识：调和级数

---

整体思路

• 题目描述不严谨，没说在无解的情况下要输出什么（比如 $n$ 个 $1$），所以我们先假设数据保证有解；
• 从 $2$ 到 $10^6$ 枚举 $x$ 作为约数，对于约数 $x$ 去扫所有 $x$ 的倍数，总共需要扫 $\frac{n}{2}+\frac{n}{3}+\frac{n}{4}+\cdots +\frac{n}{n}\approx n\ln n$ 次；
• 取所有 $x$ 的倍数在原数组中的下标，这些下标对应的数字一定同时包含 $x$ 这个约数，取这些下标中最小的两个 $id{x}_1,id{x}_2$，就是满足题意的以 $x$ 为约数的两个数的下标；
• 最后对所有约数 $x$ 取最满足题意的 $id{x}_1,id{x}_2$ 即可（如果存在多组 $i,j$，请输出 $i$ 最小的那组。如果仍然存在多组 $i,j$，请输出 $i$ 最小的所有方案中 $j$ 最小的那组。）

过题代码

#include <bits/stdc++.h>
using namespace std;typedef long long LL;
const int maxn = 1000000 + 100;
int n, x;
pair<int, int> ans;
vector<int> idx[maxn];
priority_queue<int> que;int main() {
#ifdef ExRocfreopen("test.txt", "r", stdin);
#endif // ExRocios::sync_with_stdio(false);cin >> n;ans = {n + 1, n + 1};for (int i = 1; i <= n; ++i) {cin >> x;idx[x].push_back(i);}for (int i = 1; i < maxn; ++i) {sort(idx[i].begin(), idx[i].end());while (idx[i].size() > 2) {idx[i].pop_back();}}for (int i = 2; i < maxn; ++i) {while (!que.empty()) {que.pop();}for (int j = i; j < maxn; j += i) {for (int k = 0; k < idx[j].size(); ++k) {que.push(idx[j][k]);if (que.size() > 2) {que.pop();}}}if (que.size() < 2) {continue;}int r = que.top();que.pop();int l = que.top();que.pop();if (l < ans.first) {ans = {l, r};} else if (l == ans.first) {if (r < ans.second) {ans = {l, r};}}}cout << ans.first << " " << ans.second << endl;return 0;
}