CF1154G 题解（gcd/lcm的枚举优化）

一般和 $gcd, lcm$ 相关的题，一般就 $2$ 种trick：

1. 质因子分解
2. 枚举 $gcd$ 的值

这道题是 枚举 $gcd$ 的值。因为 $lcm(a_i,a_j) = \frac{a_ia_j}{\gcd(a_i,a_j)}$，所以我们枚举一下 $gcd(a_i,a_j)$ 的值即可。

设 $g$ 为可能的 $gcd$ 的值，从 $1$ 枚举到 $10^7$，对于每一个 $g$，只要找出 最小的两个 $a_i,a_j$ 使得 $g|a_i, g|a_j$ 即可。

时间复杂度：$T(n) = \frac{10^7}{1} + \frac{10^7}{2} + … + \frac{10^7}{10^7} = 10^7(1+\frac{1}{2} + … \frac{1}{10^7}) = O(10^7 \log(10^7))$

证明正确性：

无论最终答案是什么，$\gcd(a_i,a_j)$ 必然会被枚举到。所以不会漏解。

如果我们枚举到的 $g$ 不一定是真的 $gcd$ 呢？比如 $g = 2$，然后 $a_i$ 中最小的两个倍数为 $4, 8$？

答：我们总会枚举到真正的 $gcd$，如果 $g$ 不是真实的 $gcd$，它只会比真实的 $gcd$ 更小，所以获得的 $lcm$ 更大，所以不影响答案的正确性。

另：枚举 $gcd$ 的trick之前在 Atcoder-ABC-162E 也出现过。

using namespace std;
#include <bits/stdc++.h>

#define ll long long

const int maxn = 1e6+5;
const int maxm = 1e7+5;

int arr[maxn];
int vis[maxm];   // 不要用 unordered_set, 会TLE

int n;
ll ans = 1e18;
int ai,aj;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d",&arr[i]);
        if (vis[arr[i]] && arr[i] < ans) ans = arr[i], ai = vis[arr[i]], aj = i;
        vis[arr[i]] = i;
    }

    for (int g = 1; g <= 1e7; g++) {
        int cur = 0;
        if ((g<<1) > ans) break;  // 优化时间

        for (int j = g; j <= 1e7; j += g) {
            if (vis[j]) {
                if (cur) {
                    int d = j / g;
                    ll r = 1LL * cur * d;
                    if (r < ans) {
                        ai = vis[cur];
                        aj = vis[j];
                        ans = r;
                    }
                    break;
                } else cur = j;
            }
        }
    }
    if (ai > aj) swap(ai, aj);
    printf("%d %d\n", ai,aj);
}