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

题目链接：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 ExRoc
    freopen("test.txt", "r", stdin);
#endif // ExRoc
    ios::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;
}