[алгоритмическая задача] Поиск k-периодичности
Соображение:
Нам интересны только простые эстетичности. И люстра может иметь только одну простую эстетичность или она будет 1-эстетичной.
Нам интересны только простые эстетичности. И люстра может иметь только одну простую эстетичность или она будет 1-эстетичной.
Вторая задача: смотря что значит "эффективно". Для начала можно попробовать по формуле включений и исключений.
Формула включения-исключения разве не дает ответ на второй вопрос?
А первая задача случайно решается не построением префикс-функции (или как там она называется в алгоритме Кнутта-Морисса-Пратта)?![[math]$n-\pi(n)$[/math]](mathimg.php?math=%24n-%5Cpi%28n%29%24)
даст минимальное k, если результат является делителем n.
А первая задача случайно решается не построением префикс-функции (или как там она называется в алгоритме Кнутта-Морисса-Пратта)?
Пусть N = P*Q, где P и Q - большие простые числа. Пусть все лампочки на люстре горят. Очевидно, что она будет только 1, P и Q эстетичной.
Таким образом получается, что любое число N состоящее из произведения двух простых можно разложить на множители за O(N). Сомнительно.
Таким образом получается, что любое число N состоящее из произведения двух простых можно разложить на множители за O(N). Сомнительно.
Эмм... Вообще-то даже в школе учат как за ![[math]$O(\sqrt{N})$[/math]](mathimg.php?math=%24O%28%5Csqrt%7BN%7D%29%24)
раскладывать.
даст минимальное k, если результат является делителем n.Все выдаст, если откатываться до тех пор, пока удвоенная длина преффикса больше N.
А у короля есть лишний рулон туалетной бумаги, кстати?
Первая задача — правильно.
Вторая — вероятно, так.
Вторая — вероятно, так.
Есть.
Пусть все лампочки на люстре горят. Очевидно, что она будет только 1, P и Q эстетичной.Ч0-ч0?..
а разве нет?
По условию k > 1 
мдее... давненько я в руки шашек не брал
Оставить комментарий
valodyr
Эта попроще, зато за моим авторством.В некотором королевстве местный демиург любил устраивать приёмы. Обязательным элементом таких приёмов была огромная люстра, висевшая под потолком и освещавшая гостей. Люстра представляла собой окружность, вдоль которой равномерно были распределены N лампочек.
В целях экономии король приказал зажигать не все лампочки, однако таким образом, чтобы ему нравилось. Королю нравится конфигурация включённых и выключенных лампочек тогда и только тогда, когда существует такое натуральное 1 < k < N, что k делит N и взятые подряд k лампочек имеют ту же конфигурацию, что и следующие за ними по кругу k. Назовём такую конфигурацию k-эстетичной. Например, для N = 9 конфигурация 011011011 является 3-эстетичной, а для N = 8 конфигурация 10101010 является 2-эстетичной и 4-эстетичной.
В процессе подготовки к очередному балу слуги зажгли некоторые лампочки и выписали на большой рулон туалетной бумаги число N и конфигурацию люстры в виде набора нулей и единиц. Королю необходимо за линейное относительно N время определить, для каких k такая конфигурация является k-эстетичной. Вы должны помочь величеству и вывести все такие k в порядке возрастания или слово FAIL, если таких k нет.
Ремарка: в оригинальной постановке не было про линейное время, зато было ограничение на длину входа в 10, что ли, миллионов и пара секунд на тест.
Есть и вторая задача, но я не знаю, как её эффективно решать. Для заданного N определить число эстетичных конфигураций.