G. Новый год и факторизация
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Факторизовать числа сложно. RSA Factoring Challenge предлагает $$$$100\,000$$$ тому, кто сможет факторизовать RSA-$$$1024$$$, $$$1024$$$-битное произведение двух простых чисел. До этого времени никому не удалось получить приз. Мы хотим факторизовать $$$1024$$$-битное число.

Поскольку ваш язык программирования может не предоставлять возможность работы с большими целыми числами, мы предоставим вам очень простой калькулятор.

Чтобы использовать этот калькулятор, вы можете выводить запросы и получать ответы. Операции заключаются в следующем:

  • + x y, где $$$x$$$ и $$$y$$$ — целые числа между $$$0$$$ и $$$n-1$$$. Возвращает $$$(x+y) \bmod n$$$.
  • - x y, где $$$x$$$ и $$$y$$$ — целые числа между $$$0$$$ и $$$n-1$$$. Возвращает $$$(x-y) \bmod n$$$.
  • * x y, где $$$x$$$ и $$$y$$$ — целые числа между $$$0$$$ и $$$n-1$$$. Возвращает $$$(x \cdot y) \bmod n$$$.
  • / x y, где $$$x$$$ и $$$y$$$ — целые числа между $$$0$$$ и $$$n-1$$$, а $$$y$$$ взаимно простое с $$$n$$$. Возвращает $$$(x \cdot y^{-1}) \bmod n$$$, где $$$y^{-1}$$$ — обратное к $$$y$$$ число по модулю $$$n$$$. Если $$$y$$$ не взаимно простое с $$$n$$$, тогда будет возвращено $$$-1$$$.
  • sqrt x, где $$$x$$$ — число между $$$0$$$ и $$$n-1$$$, и оно взаимно просто с $$$n$$$. Возвращает $$$y$$$ такое, что $$$y^2 \bmod n = x$$$. Если есть несколько таких целых чисел, то только одно из них будет возвращено. Если таких чисел нет, то будет возвращено $$$-1$$$.
  • ^ x y, где $$$x$$$ и $$$y$$$ — целые числа между $$$0$$$ и $$$n-1$$$. Возвращает $$${x^y \bmod n}$$$.

Найдите факторизацию $$$n$$$, которое является произведением от $$$2$$$ до $$$10$$$ различных простых чисел типа $$$4x + 3$$$, где $$$x$$$ — целое.

Из-за технических сложностей мы вынуждены ограничить количество запросов до $$$100$$$.

Входные данные

Единственная строка содержит одно целое число $$$n$$$ ($$$21 \leq n \leq 2^{1024}$$$). Гарантируется, что $$$n$$$ — произведение от $$$2$$$ до $$$10$$$ различных простых чисел типа $$$4x + 3$$$, где $$$x$$$ — целое.

Выходные данные

Вы можете вывести столько запросов, сколько пожелаете, придерживаясь ограничения по времени (смотрите раздел «Протокол взаимодействия» для более подробной информации).

Когда вы считаете, что знаете ответ, выведите ! k p_1 p_2 ... p_k, где $$$k$$$ — количество простых множителей $$$n$$$, а $$$p_i$$$ — различные простые множители. Вы можете вывести их в любом порядке.

Входные данные для взломов

Чтобы взламывать решения, используйте следующий формат:

Первая строка должна содержать $$$k$$$ ($$$2 \leq k \leq 10$$$) — количество простых чисел у факторизации $$$n$$$.

Вторая строка должна содержать $$$k$$$ целых чисел $$$p_1, p_2, \dots, p_k$$$ ($$$21 \leq n \leq 2^{1024}$$$) — простые делители $$$n$$$. Все простые числа должны быть типа $$$4x + 3$$$ для некоторого целого числа $$$x$$$. Они все должны быть различны.

Протокол взаимодействия

После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:

  • fflush(stdout) или cout.flush() в C++;
  • System.out.flush() в Java;
  • flush(output) в Pascal;
  • stdout.flush() в Python;
  • смотрите документацию для других языков.

Количество запросов не ограничено. Однако ваша программа должна (как всегда) завершиться за определенное время. Время работы интерактора также засчитывается в ограничение по времени. Максимальное время выполнения каждого запроса приведено ниже.

  • + x y — до $$$1$$$ мс.
  • - x y — до $$$1$$$ мс.
  • * x y — до $$$1$$$ мс.
  • / x y — до $$$350$$$ мс.
  • sqrt x — до $$$80$$$ мс.
  • ^ x y — до $$$350$$$ мс.

Обратите внимание, что пример ввода содержит дополнительные пустые строки, чтобы его было легче читать. Реальный ввод не будет содержать пустых строк и вам не нужно выводить дополнительные пустые строки.

Пример
Входные данные
21

7

17

15

17

11

-1

15

Выходные данные
+ 12 16

- 6 10

* 8 15

/ 5 4

sqrt 16

sqrt 5

^ 6 12

! 2 3 7
Примечание

Мы считываем с первой строки $$$n = 21$$$. Тогда мы делаем:

  1. $$$(12 + 16) \bmod 21 = 28 \bmod 21 = 7$$$.
  2. $$$(6 - 10) \bmod 21 = -4 \bmod 21 = 17$$$.
  3. $$$(8 \cdot 15) \bmod 21 = 120 \bmod 21 = 15$$$.
  4. $$$(5 \cdot 4^{-1}) \bmod 21 = (5 \cdot 16) \bmod 21 = 80 \bmod 21 = 17$$$.
  5. Квадратный корень $$$16$$$. Ответ $$$11$$$, поскольку $$$(11 \cdot 11) \bmod 21 = 121 \bmod 21 = 16$$$. Обратите внимание, что ответ также может быть равен $$$10$$$.
  6. Квадратный корень $$$5$$$. Нет таких $$$x$$$, что $$$x^2 \bmod 21 = 5$$$, значит вывод $$$-1$$$.
  7. $$$(6^{12}) \bmod 21 = 2176782336 \bmod 21 = 15$$$.

Мы пришли к выводу, что наш калькулятор работает, нужно прекратить дурачиться и понять, что $$$21 = 3 \cdot 7$$$.