CF1154G Minimum Possible LCM

给定一个由 $n$ 个整数 $a_1, a_2, \dots, a_n$ 组成的数组 $a$。 你的任务是找到一对下标 $i, j$（$1 \le i < j \le n$），使得 $lcm(a_i, a_j)$ 的值尽可能小。 $lcm(x, y)$ 表示 $x$ 和 $y$ 的最小公倍数（即最小的正整数，能够被 $x$ 和 $y$ 同时整除）。

输入的第一行包含一个整数 $n$（$2 \le n \le 10^6$），表示数组 $a$ 的元素个数。 输入的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^7$），其中 $a_i$ 表示数组 $a$ 的第 $i$ 个元素。

输出两个整数 $i$ 和 $j$（$1 \le i < j \le n$），使得 $lcm(a_i, a_j)$ 在所有合法的 $i, j$ 对中最小。如果有多组答案，可以输出任意一组。

由 ChatGPT 4.1 翻译