Наверняка вы видели безумные клипы южнокорейского рэпера PSY, такие как «Gangnam Style», «Gentleman» и «Daddy». Вы также могли слышать, что PSY пару лет назад записывал клип «Oppa Funcan Style» (к сожалению, мы не смогли найти этот клип на просторах сети; мы не исключаем, что виноват Ромкоснадзор). Мы напомним вам, как выглядел этот хит (оригинальное описание можно прочитать здесь).
На площадке есть \(n\) платформ, пронумерованных целыми числами от \(1\) до \(n\), на \(i\)-й платформе стоит танцор с номером \(i\). Далее, каждую секунду все танцоры, стоявшие на платформе с номером \(i\), перепрыгивают на платформу с номером \(f(i)\). Правило перемещения \(f\) выбирается заранее и не меняется на протяжении клипа.
Продолжительность клипа составляла \(k\) секунд, и правило \(f\) было выбрано таким образом, чтобы в конце клипа (через \(k\) секунд) все танцоры оказались на своих изначальных местах (то есть танцор номер \(i\) должен оказаться на платформе с номером \(i\)). Это позволило зациклить клип и собрать ещё больше лайков.
PSY знает, что сейчас всё большую популярность набирают улучшенные версии старых произведений искусства, поэтому он решил выпустить remastered-версию своего клипа двухлетней давности.
В данном случае «улучшенная версия» подразумевает ещё больше безумия, и количество платформ может достигать \(10^{18}\)! Однако режиссёр клипа говорит, что если какой-то танцор будет оставаться на одной и той же платформе, то зритель заскучает и сразу выключит клип. Поэтому для всех \(x\) от \(1\) до \(n\) должно быть выполнено \(f(x) \neq x\).
Немалая часть успеха классического клипа была в том, что его удалось зациклить, поэтому для remastered-версии это также должно быть выполнено.
PSY ещё не определился с точным количеством платформ и продолжительностью клипа, поэтому он просит вас для разных вариантов определить, существует ли подходящее правило \(f\).