На соревновании SNSS 2012 Round 1 была одна задача по теории чисел.
К сожалению, никаких адекватных идей в первое время не придумалось и осознавая, что мои знания в этой области ну совсем скудные (особенно что касается модулярной арифметики в широком смысле), было решено почитать Кормена.
Читал я главы по теории чисел 3 дня.
В результате, были прочитаны и осознаны такие важные вещи как группы и подгруппы, функция Эйлера, расширенный алгоритм Евклида и решение линейных диофантовых уравнений, поиск обратного элемента в кольце, Китайская теорема об остатках, возведение в степень по модулю, вычисление квадратного корня из элемента в кольце.
Под конец начало складываться ощущение, что перечитал курс лекций по теоретическим основам криптографии :-).
Для закрепления почти всех данных тем рискнул решать задачу с Тимуса 1132. Квадратный корень.
В результате на практике были реализованы поиск обратного элемента в кольце, быстрое возведение в степень в кольце, нахождение обратного элемента в кольце через "расширенный" алгоритм Евклида (как оказалось та версия, которая написана в Кормене, лучше поддаётся реализации на Java, чем попытки перевести то, что есть на e-maxx.ru.
Пока ещё свежи воспоминания, хотелось бы упомянуть пару моментов, касающихся производительности.
В классе BigInteger есть такие процедуры, как modInverse, modPow с весьма говорящими названиями.
Как оказалось, ручная версия modPow в той задаче даёт почти двухкратный выигрыш в скорости. Переписанная modInverse тоже дала прирост, но используется она там не так часто.
В общем, данные функции использовать можно, но на производительность потом не жалуйтесь :-)
Однако, стоит признаться, что данную задачу ИМХО практически нереально решить самому.
Мне пришлось воспользоваться одной лекций.
Посмотрев форум, мои подозрения насчёт "ни разу не халявы" утвердились.
Так что если откинуть теоретическое обоснование решения, то мы получим не плохую тренировку написания вышеуказанных высокопроизводительных алгоритмов, что тоже не плохо.
PS:
Сейчас моё решение - Top3 решений на Java по данной задаче :-)
К сожалению, никаких адекватных идей в первое время не придумалось и осознавая, что мои знания в этой области ну совсем скудные (особенно что касается модулярной арифметики в широком смысле), было решено почитать Кормена.
Читал я главы по теории чисел 3 дня.
В результате, были прочитаны и осознаны такие важные вещи как группы и подгруппы, функция Эйлера, расширенный алгоритм Евклида и решение линейных диофантовых уравнений, поиск обратного элемента в кольце, Китайская теорема об остатках, возведение в степень по модулю, вычисление квадратного корня из элемента в кольце.
Под конец начало складываться ощущение, что перечитал курс лекций по теоретическим основам криптографии :-).
Для закрепления почти всех данных тем рискнул решать задачу с Тимуса 1132. Квадратный корень.
В результате на практике были реализованы поиск обратного элемента в кольце, быстрое возведение в степень в кольце, нахождение обратного элемента в кольце через "расширенный" алгоритм Евклида (как оказалось та версия, которая написана в Кормене, лучше поддаётся реализации на Java, чем попытки перевести то, что есть на e-maxx.ru.
Пока ещё свежи воспоминания, хотелось бы упомянуть пару моментов, касающихся производительности.
В классе BigInteger есть такие процедуры, как modInverse, modPow с весьма говорящими названиями.
Как оказалось, ручная версия modPow в той задаче даёт почти двухкратный выигрыш в скорости. Переписанная modInverse тоже дала прирост, но используется она там не так часто.
В общем, данные функции использовать можно, но на производительность потом не жалуйтесь :-)
Однако, стоит признаться, что данную задачу ИМХО практически нереально решить самому.
Мне пришлось воспользоваться одной лекций.
Посмотрев форум, мои подозрения насчёт "ни разу не халявы" утвердились.
Так что если откинуть теоретическое обоснование решения, то мы получим не плохую тренировку написания вышеуказанных высокопроизводительных алгоритмов, что тоже не плохо.
PS:
Сейчас моё решение - Top3 решений на Java по данной задаче :-)
Комментариев нет:
Отправить комментарий