汉阳网站建设谷歌seo优化排名
题目链接：https://www.lanqiao.cn/problems/3525/learning/
个人评价：难度 2 星（满星：5）
前置知识：调和级数
整体思路
- 题目描述不严谨，没说在无解的情况下要输出什么（比如 n n n 个 1 1 1），所以我们先假设数据保证有解；
- 从 2 2 2 到 1 0 6 10^6 106 枚举 x x x 作为约数，对于约数 x x x 去扫所有 x x x 的倍数，总共需要扫 n 2 + n 3 + n 4 + ⋯ + n n ≈ n ln n \frac{n}{2}+\frac{n}{3}+\frac{n}{4}+\cdots+\frac{n}{n}\approx n\ln n 2n+3n+4n+⋯+nn≈nlnn 次；
- 取所有 x x x 的倍数在原数组中的下标，这些下标对应的数字一定同时包含 x x x 这个约数，取这些下标中最小的两个 i d x 1 , i d x 2 idx_1,idx_2 idx1,idx2，就是满足题意的以 x x x 为约数的两个数的下标；
- 最后对所有约数 x x x 取最满足题意的 i d x 1 , i d x 2 idx_1,idx_2 idx1,idx2 即可（如果存在多组 i , j i,j i,j，请输出 i i i 最小的那组。如果仍然存在多组 i , j i,j i,j，请输出 i i i 最小的所有方案中 j j 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;
}