Факторизовать числа сложно. 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\).
Выходные данные
Вы можете вывести столько запросов, сколько пожелаете, придерживаясь ограничения по времени (смотрите раздел «Протокол взаимодействия» для более подробной информации).
Когда вы считаете, что знаете ответ, выведите ! 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\) мс.
Обратите внимание, что пример ввода содержит дополнительные пустые строки, чтобы его было легче читать. Реальный ввод не будет содержать пустых строк и вам не нужно выводить дополнительные пустые строки.
Примечание
Мы считываем с первой строки \(n = 21\). Тогда мы делаем:
- \((12 + 16) \bmod 21 = 28 \bmod 21 = 7\).
- \((6 - 10) \bmod 21 = -4 \bmod 21 = 17\).
- \((8 \cdot 15) \bmod 21 = 120 \bmod 21 = 15\).
- \((5 \cdot 4^{-1}) \bmod 21 = (5 \cdot 16) \bmod 21 = 80 \bmod 21 = 17\).
- Квадратный корень \(16\). Ответ \(11\), поскольку \((11 \cdot 11) \bmod 21 = 121 \bmod 21 = 16\). Обратите внимание, что ответ также может быть равен \(10\).
- Квадратный корень \(5\). Нет таких \(x\), что \(x^2 \bmod 21 = 5\), значит вывод \(-1\).
- \((6^{12}) \bmod 21 = 2176782336 \bmod 21 = 15\).
Мы пришли к выводу, что наш калькулятор работает, нужно прекратить дурачиться и понять, что \(21 = 3 \cdot 7\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|