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).


-----Input-----

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$.


-----Output-----

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.


-----Examples-----
Input
5
2 4 8 3 6

Output
1 2

Input
5
5 2 11 3 7

Output
2 4

Input
6
2 5 10 1 10 2

Output
1 4

Difficulty: HARD
Tags: Number theory

Complete search

Mathematics

Greedy algorithms
Skill types: Complete search

Greedy algorithms

Starter code:

Solutions:
import os, sys
from io import BytesIO, IOBase
from array import array

def main():
	INF = 10 ** 18
	n = int(input())
	a = list(map(int, input().split()))
	lim = max(a) + 1
	counter = array('i', [0] * lim)
	for i in a:
		counter[i] += 1
	mini = INF
	for i in range(1, lim):
		(m, m1) = (INF, INF)
		for j in range(i, lim, i):
			if counter[j] >= 2:
				(m, m1) = (min(m, j), j)
				break
			if counter[j] == 1:
				(m, m1) = (j, m)
				if m1 != INF:
					break
		z = m * m1 // i
		if z < mini:
			(mini, n1, n2) = (z, m, m1)
	(ind1, ind2) = (-1, -1)
	for i in range(n):
		if ind1 == -1 and n1 == a[i]:
			ind1 = i + 1
		elif ind2 == -1 and n2 == a[i]:
			ind2 = i + 1
	if ind1 > ind2:
		(ind1, ind2) = (ind2, ind1)
	print(ind1, ind2)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


__version__ = '3.4'
__date__ = '2019-04-17'
import sys

def find_minimum_lcm(n, integers):
	already_seen = [0] * 10000001
	repeated_value = 10000001 * 10000001
	repeated_indices = None
	for (index, value) in enumerate(integers):
		if already_seen[value]:
			if value < repeated_value:
				repeated_value = value
				repeated_indices = (index, already_seen[value] - 1)
		else:
			already_seen[value] = index + 1
	answer_value = repeated_value
	answer_indices = repeated_indices
	sorted_integers = sorted(integers)
	(min_1, min_2) = sorted_integers[:2]
	if min_1 == min_2:
		return sorted(repeated_indices)
	else:
		factor_lcm = min_1 * min_2
		if factor_lcm < answer_value:
			answer_value = factor_lcm
			answer_indices = (already_seen[min_1] - 1, already_seen[min_2] - 1)
	for factor in range(2, 10000001):
		if factor > answer_value:
			break
		seen_once = -1
		for multiple in range(max(1, min_1 // factor) * factor, 10000001, factor):
			if already_seen[multiple]:
				if seen_once > 0:
					factor_lcm = seen_once * multiple // factor
					if factor_lcm < answer_value:
						answer_value = factor_lcm
						answer_indices = (already_seen[seen_once] - 1, already_seen[multiple] - 1)
					break
				else:
					seen_once = multiple
	return sorted(answer_indices)

def main(argv=None):
	n = int(input())
	integers = list(map(int, input().split()))
	(i, j) = find_minimum_lcm(n, integers)
	print('{0} {1}'.format(i + 1, j + 1))
	return 0
STATUS = main()
sys.exit(STATUS)


import math
from collections import defaultdict
import sys
input = sys.stdin.readline

def main():
	n = int(input())
	a = list(map(int, input().split()))
	MAX = 10 ** 7 + 1
	res = MAX * MAX
	MAX_P = 3163
	primes = []
	p = 2
	sieve = [True] * (MAX_P + 1)
	while p < MAX_P:
		if sieve[p]:
			primes.append(p)
			k = 2
			while k * p < MAX_P:
				sieve[k * p] = False
				k += 1
		p += 1
	np = len(primes)
	cand1 = {}
	cand2 = {}
	ind1 = {}
	ind2 = {}
	res = MAX * MAX
	for index in range(n):
		val = a[index]
		if val >= res:
			continue
		divisors = [1]
		p = 0
		while val > 0 and p < np:
			while val % primes[p] == 0:
				divisors += [d * primes[p] for d in divisors]
				val //= primes[p]
			p += 1
		if val > 1:
			divisors += [d * val for d in divisors]
		for d in set(divisors):
			if d not in cand1:
				cand1[d] = a[index]
				ind1[d] = index
			else:
				if d not in cand2:
					if a[index] < cand1[d]:
						cand2[d] = cand1[d]
						ind2[d] = ind1[d]
						cand1[d] = a[index]
						ind1[d] = index
					else:
						cand2[d] = a[index]
						ind2[d] = index
				elif a[index] < cand1[d]:
					cand2[d] = cand1[d]
					ind2[d] = ind1[d]
					cand1[d] = a[index]
					ind1[d] = index
				elif a[index] < cand2[d]:
					cand2[d] = a[index]
					ind2[d] = index
				else:
					continue
				if res > cand1[d] // d * cand2[d]:
					(x, y) = (ind1[d], ind2[d])
					res = cand1[d] // d * cand2[d]
	print(min(x + 1, y + 1), max(x + 1, y + 1))

def __starting_point():
	main()
__starting_point()