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

Tavrida NU Akai contest. Petrozavodsk training camp. Summer 2010

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

D. Случайный порядок песен

Ограничение времени: 0.5 секунды
Ограничение памяти: 64 МБ
Однажды Саша решил, что случайный порядок, в котором проигрывает песни его любимый медиаплеер, никуда не годится, и его нужно изменить. Саша хочет вычислять номера песен по следующему правилу:
x0 = 0,
xi = (xi − 1 · a + b) mod m,
где m — это общее количество песен, а a и b — числа от 0 до m − 1. Сгенерированная последовательность номеров должна удовлетворять следующим правилам:
  • x0xm − 1 должны являться перестановкой чисел от 0 до m − 1,
  • xm должно быть равно нулю.
Саша захотел вычислить все пары значений (ai, bi), дающие требуемые последовательности, и вычислить среднее арифметическое среди всех чисел ai в этих парах. Помогите ему!

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

Входные данные состоят не более чем из 100 тестов. Каждый тест представляет собой единственное целое число m (1 < m < 109), записанное в отдельной строке.

Результат

Выведите для каждого теста в отдельной строке среднее арифметическое чисел ai, округлённое вниз.

Пример

исходные данныерезультат
2
36
100
123
1
13
41
1
Источник задачи: Tavrida NU Akai Contest. Petrozavodsk Summer Session, August 2010.
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1813. Случайный порядок песен