D. НОД

Имя входного файла: gcd.in
Имя выходного файла: gcd.out
Ограничение по времени: 2 s
Ограничение по памяти: 256 megabytes

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

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

В первой строке входного файла находится натуральное число n – изначальное количество элементов в наборе, (2 ≤ n ≤ 100000). Во второй строке находится n чисел a1, a2, …, an – изначальный набор a, (1 ≤ ai ≤ 109).

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

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

Пример:

gcd.ingcd.out
4 4 1 4 8 2 4

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


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

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



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