← 返回题目列表

Codeforces · 1091/G

G. 新年与分解合作

中文机器翻译题面 查看原题

整数因式分解很困难。 RSA 分解挑战赛提供 $$$$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$$$ 之间不同素数的乘积,对于某个整数 $$$x$$$,所有素数的形式都是 $$$4x + 3$$$。

由于技术问题,我们将请求数量限制为 $$$100$$$。

输入

唯一一行包含一个整数 $$$n$$$ ($$$21 \leq n \leq 2^{1024}$$$)。保证 $$$n$$$ 是 $$$2$$$ 和 $$$10$$$ 之间不同素数的乘积,对于某个整数 $$$x$$$,所有素数的形式都是 $$$4x + 3$$$。

互动

打印查询后,不要忘记输出行尾并刷新输出。否则您将超出空闲限制。为此,请使用:

- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。

查询次数不限。但是,您的计划必须(一如既往)符合时间限制。交互器的运行时间也计入时间限制。下面给出了每个查询的最大运行时间。

- + x y — 最多 $$$1$$$ 毫秒。
- - x y — 最多 $$$1$$$ 毫秒。
- * x y — 最多 $$$1$$$ 毫秒。
- / x y — 最多 $$$350$$$ 毫秒。
- sqrt x — 最多 $$$80$$$ 毫秒。
- ^ x y — 最多 $$$350$$$ 毫秒。

请注意,示例输入包含额外的空行,以便于阅读。真实的输入不会包含任何空行,您不需要输出额外的空行。

输出

您可以在遵守时间限制的情况下打印任意数量的查询(有关更多详细信息,请参阅“交互”部分)。

当你认为你知道答案时,输出一行表格! k p_1 p_2 ... p_k,其中 $$$k$$$ 是 $$$n$$$ 的质因数,$$$p_i$$$ 是不同的质因数。您可以按任何顺序打印因子。

黑客输入

对于 hack,请使用以下格式:.

第一个应该包含 $$$k$$$ ($$$2 \leq k \leq 10$$$) — $$$n$$$ 的质因数的数量。

第二个应包含 $$$k$$$ 空格分隔的整数 $$$p_1, p_2, \dots, p_k$$$ ($$$21 \leq n \leq 2^{1024}$$$) - $$$n$$$ 的质因数。对于某个整数 $$$x$$$,所有质因数都必须采用 $$$4x + 3$$$ 的形式。它们都必须是独特的。

示例

输入 #1

21
7
17
15
17
11
-1
15

输出 #1

+ 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$$$。