C. 公因数匹配

传统题

1000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

问题描述

给定 $n$ 个正整数 $A_i$ ，请找出两个数 $i$ ， $j$ 使得 $i<j$ 且 $A_i$ 和 $A_j$ 存在大于 $1$ 的公因数。

如果存在多组 $i$ ， $j$ ，请输出 $i$ 最小的那组。如果仍然存在多组 $i$ ， $j$ ，请输出 $i$ 最小的所有方案中 $j$ 最小的那组。

输入的第一行包含一个整数 $n$ 。

第二行包含 $n$ 个整数分别表示 $A_1，A_2，…，A_n$ ，相邻整数之间使用一个空格分隔。

输出一行包含两个整数分别表示题目要求的 $i$ ， $j$ ，用一个空格分隔。

5
5 3 2 6 9

2 4

对于 $40\%$ 的评测用例， $n≤5000$ ；

对于所有评测用例， $1≤n≤10^5$ ， $1≤A_i≤10^6$ 。