0375. НОД

Анна Сергеевна – преподаватель математики средней школы в одном провинциальном мегаполисе. Следующее занятие в пятом классе будет посвящено нахождению наибольшего общего делителя.
Анна хочет дать детям задание на вычисление наибольшего общего делителя некоторого набора чисел. Для этого она выписала набор n чисел, но потом осознала, что n чисел – это слишком много для пятиклассника, поэтому она хочет удалить одно число из набора так, чтобы наибольший общий делитель оставшихся чисел был бы максимально возможным.
Анна Сергеевна и сама бы справилась с этой простой задачей, но очень устала, поэтому она просит вас помочь ей.

Формат входного файла

В первой строке входного файла находится натуральное число n – изначальное количество элементов в наборе, (2 ≤ n ≤ 100000). Во второй строке находится n чисел a₁, a₂, …, a_n – изначальный набор a, (1 ≤ a_i ≤ 10⁹).

Формат выходного файла

В единственной строке выходного файла выведите два числа – индекс удаляемого элемента из набора и наибольший общий делитель оставшегося набора чисел. Если ответов несколько, то выведите тот, где индекс удаляемого элемента наименьший.

Пример:

В примере после удаления числа 1 останется набор 4 4 8, наибольший общий делитель в котором равен 4.

Источник: Открытый весенний чемпионат ПетрГУ по программированию, 20 апреля 2014

Обсудить       Отправить решение



Версия для печати