ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Уральская региональная командная олимпиада по программированию 2013

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

D. Простая магия

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Вы думаете, что магия — простая штука? Помахал себе руками, пробубнил непонятные слова — и всё готово, вокруг расцветают дивные сады, а во врага несется сметающий всё на своём пути файрболл.
На самом деле всё куда сложнее. Чтобы достичь мастерства, юные волшебники годами изучают такие дисциплины, как магический анализ и прикладная демонология.
Например, прямо сейчас Олег, студент института магии и колдовских наук (ИМКН), готовится к экзамену. И у него ну никак не получается взять определитель Дамблдора. Как вы, наверное, уже догадались, Олег попросил помощи именно у вас.
На случай, если вы прогуливали пары по теории нелинейных заклинаний, кратко напомним вам основные определения. По теореме Гэндальфа, любая часть подпространства может быть представлена в виде вектора магических потенциалов — попросту говоря, массива из n целых положительных чисел. Определитель Дамблдора от этого массива равен минимальному количеству элементарных магических преобразований, необходимых для превращения исходного массива в массив, в котором все элементы равны единице. Одно элементарное магическое преобразование превращает исходный массив длины k в новый массив длины k · (k − 1) / 2, при этом элементами нового массива являются наибольшие общие делители каждой пары элементов исходного массива. Например, массив {2, 3, 3, 6} после применения элементарного магического преобразования превращается в массив {НОД(2, 3), НОД(2, 3), НОД(2, 6), НОД(3, 3), НОД(3, 6), НОД(3, 6)}, то есть в {1, 1, 2, 3, 3, 3}.

Исходные данные

В первой строке дано число n — количество чисел в исходном массиве (3 ≤ n ≤ 10 000). В следующих n строках записаны элементы массива — целые положительные числа, не превосходящие 107.

Результат

В единственной строке выведите значение определителя Дамблдора для исходного массива. Если определитель не определён или превосходит 1018, выведите «infinity».

Примеры

исходные данныерезультат
3
1
2
3
1
4
2
2
2
2
infinity
Автор задачи: Кирилл Бороздин
Источник задачи: Уральская региональная командная олимпиада по программированию 2013
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 2003. Простая магия