Задача состоит в следующем: учитывая положительное целое число x
и простое число n > x
, выведите наименьшее положительное целое число, y
такое что (y * y) mod n = x
. Важной частью этого вопроса является срок, указанный ниже, который исключает грубые решения.
Если такого значения нет, y
ваш код должен выводиться N
.
Контрольные примеры
(2, 5, N),
(3, 5, N),
(4, 5, 2),
(524291, 1048583, N),
(529533, 1048583, N),
(534775, 1048583, 436853),
(540017, 1048583, 73675),
(536870913, 1073741827, 375394238),
(542239622, 1073741827, 267746399),
(547608331, 1073741827, N),
(552977040, 1073741827, 104595351),
(1099511627676, 1099511627791, N),
(1099511627677, 1099511627791, 269691261521),
(1099511627678, 1099511627791, 413834069585),
(1267650600228229401496703204376, 1267650600228229401496703205653, 5312823546347991512233563776),
(1267650600228229401496703204476, 1267650600228229401496703205653, N)
(1267650600228229401496703204576, 1267650600228229401496703205653, N)
(1267650600228229401496703204676, 1267650600228229401496703205653, 79905476259539917812907012931)
Вход и выход
Вы можете принимать и выводить данные любым удобным для вас способом. Если вам не нравится вывод, N
тогда Falsey
подойдет любое значение.
ограничения
Ваш код должен отвечать на все тесты менее чем за 1 минуту на стандартном рабочем столе. Это ограничение по времени только для предотвращения грубых ответов, и я ожидаю, что хорошие ответы начнутся практически мгновенно. Вы не можете использовать какую-либо библиотеку или встроенную программу, которая решает эту проблему или проверяет, является ли число квадратичным остатком.
1267650600228229401496703205653
себя или если у вас есть поддержка 128 бит, например,__int128
в gcc. Существует также ряд 256-битных библиотек int для различных языков. Наконец, многие языки имеют произвольную точность в библиотеке.Ответы:
Pyth,
8382 байтаТестирование
Эта программа реализует алгоритм Тонелли-Шанкса . Я написал это, внимательно следя за страницей Википедии. Это берет как вход
(n, p)
.Об отсутствии квадратного корня сообщает следующая ошибка:
Это очень сложный гольф-код, написанный в императивном стиле, в отличие от более распространенного функционального стиля Pyth.
Я использую один тонкий аспект Pyth
=
, который, если за ним сразу не следует переменная, ищет в программе следующую переменную, затем присваивает результат следующего выражения этой переменной, а затем возвращает этот результат. На протяжении всего объяснения я буду ссылаться на страницу википедии: алгоритм Тонелли-Шенкса , поскольку именно этот алгоритм я реализую.Объяснение:
A
принимает 2-кортеж в качестве входных данных, присваивает значенияG
и,H
соответственно, и возвращает свои входные данные.Q
это начальный вход.e
возвращает последний элемент последовательности. После этого фрагмента кода,G
этоn
иH
иQ
естьp
.M
определяет функцию 2 входовg
, где входыG
иH
..^
является быстрой модульной функцией возведения в степень Пита. Этот фрагмент определяет,g
чтобы означать мод возведения в степеньQ
.f
определяет цикл повторения до false и возвращает количество итераций, для которых он выполняется, в1
качестве входных данных. Во время каждой итерации цикла мы делимH
на 2, устанавливаемH
это значение и проверяем, является ли результат нечетным. Как только это произойдет, мы остановимся.K
хранит количество итераций, которые это заняло.Одна очень хитрая вещь -
=2;
бит.=
выполняет поиск следующей переменной, котораяT
, следовательно,T
имеет значение 2. ОднакоT
внутриf
цикла находится счетчик итераций, поэтому мы используем его;
для получения значенияT
из глобальной среды. Это сделано для того, чтобы сэкономить пару байтов пробела, которые в противном случае были бы необходимы для разделения чисел.После этого фрагмента,
K
этоS
из википедии статьи (вики), иH
этоQ
с вики, иT
является2
.Теперь нам нужно найти квадратичный мод без остатка
p
. Мы будем грубо форсировать это, используя критерий Эйлера./Q2
есть(p-1)/2
, так как/
это деление по полам, поэтомуftgT/Q;1
находит первое целое число,T
гдеT ^ ((p-1)/2) != 1
, как желательно. Напомним, что;
снова тянетT
из глобальной среды, которая по-прежнему 2. Это результатz
из вики.Далее, чтобы создать
c
из вики, нам нужноz^Q
, поэтому мы оборачиваем вышеупомянутоеg ... H
и присваиваем результатT
. ТеперьT
этоc
из вики.Давайте выделим это:
~gGH
.~
похоже=
, но возвращает исходное значение переменной, а не ее новое значение. Таким образом, он возвращаетG
, чтоn
из вики.Это присваивает
J
значениеn^((Q+1)/2)
, котороеR
из вики.Теперь вступает в силу следующее:
Это присваивает
G
значениеn^Q
, котороеt
из вики.Теперь у нас есть переменные цикла.
M, c, t, R
из вики естьK, T, G, J
.Тело цикла сложное, поэтому я собираюсь представить его с пробелами так, как я написал:
Сначала мы проверяем,
G
равен ли 1. Если это так, мы выходим из цикла.Следующий код, который выполняется:
Здесь мы ищем первое значение
i
, котороеG^(2^i) mod Q = 1
начинается с 1. Результат сохраняется вK
.Здесь мы берем старое значение
K
, вычитаем новое значениеK
, вычитаем 1, повышаем 2 до этой степени, а затем повышаемT
до этого значения мощностиQ
, а затем присваиваем результатT
. Это делаетT
равнымb
из вики.Это также строка, которая завершает цикл и завершается ошибкой, если нет решения, потому что в этом случае новое значение
K
будет равно старому значениюK
, 2 будет повышено до-1
, и модульное возведение в степень вызовет ошибку.Затем мы умножаем
J
на результат выше и сохраняем егоJ
, сохраняя вR
курсе.Затем мы возводим в квадрат
T
и сохраняем результат обратноT
, устанавливаяT
обратноc
из вики.Затем мы умножаем
G
на этот результат, берем его модQ
и сохраняем результат обратноG
.И мы завершаем цикл.
После того, как цикл закончен,
J
это квадратный корень изn
модаp
. Чтобы найти самый маленький, мы используем следующий код:_BJ
создает списокJ
и его отрицание,%
неявно принимает вQ
качестве второго аргумента и использует поведение Pyth по умолчанию для применения% ... Q
к каждому члену последовательности. ЗатемS
сортирует список иh
принимает его первый член, минимум.источник
Python 2, 166 байт
источник
%timeit Q(1267650600228229401496703204676,1267650600228229401496703205653) 100 loops, best of 3: 2.83 ms per loop
:)SageMath , 93 байта
Снижение до более сложной проблемы, для которой у SageMath достаточно быстрых встроенных функций.
Попробуйте это на SageMathCell
источник
Haskell , 326 байт
Обычно мне нравятся грубые ответы. Поскольку это сильно обескураживает из-за ограничения по времени, вот самый эффективный способ, который я знаю:
Попробуйте онлайн!
Я уверен, что это может быть продолжено, но это должно сделать пока.
источник
testCases
на те из оригинального TIO, которые едва ли вписываются в комментарий даже без них.testCases
.