caxapa.ru :: Ну да, про бесконечность - это от разворачивания mod, дальше понятно, что надо накладывать ограничения задачи. Но как-то оно явно не хочет быть симметричным по затратам.

ReAl (01.04.2009 16:17, просмотров: 204) ответил Рэйлвэй Каген на K<(N-1)/2, а если учесть, что К-целое, то N/2 надо бы исключить. Но это несущественно сократит поиск.

Ну да, про бесконечность - это от разворачивания mod, дальше понятно, что надо накладывать ограничения задачи. Но как-то оно явно не хочет быть симметричным по затратам.

Ответить

- Вот еще что придумал: y(x) = (y(x-1) + x) mod N. Поэтому если из y вычитать по модулю N числа 1,2,3,4, то на шаге x получится ноль. То же количество итераций, что и перебором, но вместо умножения x и деления на 2 - вычитание. - Сергей Борщ(02.04.2009 03:22)
  - Решение найдено. Спасибо коллегам с Электроникса, которые напрягли математиков на форуме НГУ :) Если кому интересно - по ссылке. - Сергей Борщ(02.04.2009 18:39, ссылка)
    - Развернул рекурсию. Это какой же склад ума надо уметь, чтобы писать рекурсию прямо из головы? Сергей Борщ(387 знак., 04.04.2009 13:04)
      - Вполне обычный. Мы тут все забыли, как складывать лист бумаги :). А оно вон как выходит -> - Рэйлвэй Каген(04.04.2009 14:45, картинка)
    - Класс! - Рэйлвэй Каген(03.04.2009 09:03)

Средства и методы разработки