Codeforces 1154G（枚举）

我预处理\(1e7log(1e7)\)的因数被T掉了，就不敢往这个复杂度想了……无奈去看AC代码

结果怎么暴举gcd剪一剪小枝就接近3s卡过去了！vector有锅（确信

const int maxn = 1e6 + 5, maxa = 1e7 + 5;
int n, a, l, r;
ll lcm = INF;
int f[maxa], s[maxa];int main() {
read(n);
rep(i, 1, n) {
read(a);
if (f[a])s[a] = i;
elsef[a] = i;
}
rep(d, 1, maxa - 5) {
vector<pii> v;
for (int j = 1; j * d <= maxa - 5; j++) {
if (v.size() >= 2)break;
if (f[j * d])v.push_back({j * d, f[j * d]});
if (s[j * d])v.push_back({j * d, s[j * d]});
}
if (v.size() < 2)continue;
ll tmp = (ll)v[0].first / d * v[1].first;
if (lcm > tmp) {
lcm = tmp;
l = v[0].second;
r = v[1].second;
}
}
if (l > r)swap(l, r);
printf("%d %d\n", l, r);
return 0;
}