306155: CF1154G. Minimum Possible LCM

Memory Limit:1024 MB Time Limit:4 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Minimum Possible LCM

题意翻译

## Description 给定一个长度为 $n$ 的序列 $a$,找出两个数,最小化他们的最小公倍数 ## Input 第一行是一个整数 $n$ 下面一行 $n$ 个整数描述这个序列 ## Output 输出一行两个整数代表这两个数在序列中的位置。如果有多解则任意输出一个即可。 ## Limitation $2~\leq~n~\leq~10^6$ $1~\leq~a_i~\leq~10^7$ Translated By @ 一扶苏一

题目描述

You are given an array $ a $ consisting of $ n $ integers $ a_1, a_2, \dots, a_n $ . Your problem is to find such pair of indices $ i, j $ ( $ 1 \le i < j \le n $ ) that $ lcm(a_i, a_j) $ is minimum possible. $ lcm(x, y) $ is the least common multiple of $ x $ and $ y $ (minimum positive number such that both $ x $ and $ y $ are divisors of this number).

输入输出格式

输入格式


The first line of the input contains one integer $ n $ ( $ 2 \le n \le 10^6 $ ) — the number of elements in $ a $ . The second line of the input contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le 10^7 $ ), where $ a_i $ is the $ i $ -th element of $ a $ .

输出格式


Print two integers $ i $ and $ j $ ( $ 1 \le i < j \le n $ ) such that the value of $ lcm(a_i, a_j) $ is minimum among all valid pairs $ i, j $ . If there are multiple answers, you can print any.

输入输出样例

输入样例 #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

Input

题意翻译

## Description 给定一个长度为 $n$ 的序列 $a$,找出两个数,最小化他们的最小公倍数 ## Input 第一行是一个整数 $n$ 下面一行 $n$ 个整数描述这个序列 ## Output 输出一行两个整数代表这两个数在序列中的位置。如果有多解则任意输出一个即可。 ## Limitation $2~\leq~n~\leq~10^6$ $1~\leq~a_i~\leq~10^7$ Translated By @ 一扶苏一

加入题单

上一题 下一题 算法标签: