← 返回题目列表

Codeforces · 1154/G

G. 最小可能的 LCM

中文机器翻译题面 查看原题

给定一个数组 $$$a$$$,由 $$$n$$$ 整数 $$$a_1、a_2、\dots、a_n$$$ 组成。

你的问题是找到这样一对索引 $$$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$$$ 中最小。如果有多个答案,您可以打印任何一个。

示例

输入 #1

5
2 4 8 3 6

输出 #1

1 2

输入 #2

5
5 2 11 3 7

输出 #2

2 4

输入 #3

6
2 5 10 1 10 2

输出 #3

1 4