CF1091G New Year and the Factorisation Collaboration

整数分解是一个困难的问题。RSA 分解挑战为分解 RSA-$1024$（一个 $1024$ 位的两个素数的乘积）提供了 $100\,000 美元$ 的奖金。至今，尚无人能够获得该奖金。现在我们希望你分解一个 $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$，其中 $n$ 是 $2$ 到 $10$ 个不同素数的乘积，且所有素数均为形如 $4x+3$ 的数。 由于技术原因，查询次数限制为 $100$ 次。

仅一行，包含一个整数 $n$（$21 \leq n \leq 2^{1024}$）。保证 $n$ 是 $2$ 到 $10$ 个不同素数的乘积，且所有素数均为形如 $4x+3$ 的数。

你可以根据需要输出任意多次查询，但需遵守时间限制（详见交互部分）。 当你认为已经得到了答案时，输出一行，格式为：! k p\_1 p\_2 ... p\_k，其中 $k$ 是 $n$ 的素因数个数，$p_i$ 是不同的素因数。素因数顺序不限。 Hack 输入 对于 Hack，使用如下格式： 第一行包含 $k$（$2 \leq k \leq 10$）——$n$ 的素因数个数。 第二行包含 $k$ 个用空格分隔的整数 $p_1, p_2, \dots, p_k$（$21 \leq n \leq 2^{1024}$）——$n$ 的素因数。所有素因数均为形如 $4x+3$ 的数，且互不相同。 交互说明 每次输出查询后，别忘了输出换行并刷新输出缓冲区，否则会因“Idleness limit exceeded”而被判错。具体方法如下： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其他语言请查阅相关文档 查询次数不作限制，但程序必须在时限内完成。判题器的运行时间也计入总时限。每种操作的最大运行时间如下： - `+ x y` — 最多 $1$ ms - `- x y` — 最多 $1$ ms - `* x y` — 最多 $1$ ms - `/ x y` — 最多 $350$ ms - `sqrt x` — 最多 $80$ ms - `^ x y` — 最多 $350$ ms 注意，样例输入中包含了额外的空行以便于阅读。实际输入不会包含空行，你也无需输出多余的空行。

我们从读取第一行的整数 $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$。 由 ChatGPT 4.1 翻译