CF1091G.New Year and the Factorisation Collaboration

Integer factorisation is hard. The RSA Factoring Challenge offered $$100\,000$ for factoring RSA-$1024$, a $1024$-bit long product of two prime numbers. To this date, nobody was able to claim the prize. We want you to factorise a $1024$-bit number.

Since your programming language of choice might not offer facilities for handling large integers, we will provide you with a very simple calculator.

To use this calculator, you can print queries on the standard output and retrieve the results from the standard input. The operations are as follows:

• + x y where $x$ and $y$ are integers between $0$ and $n-1$. Returns $(x+y) \bmod n$.
• - x y where $x$ and $y$ are integers between $0$ and $n-1$. Returns $(x-y) \bmod n$.
• * x y where $x$ and $y$ are integers between $0$ and $n-1$. Returns $(x \cdot y) \bmod n$.
• / x y where $x$ and $y$ are integers between $0$ and $n-1$ and $y$ is coprime with $n$. Returns $(x \cdot y^{-1}) \bmod n$ where $y^{-1}$ is multiplicative inverse of $y$ modulo $n$. If $y$ is not coprime with $n$, then $-1$ is returned instead.
• sqrt x where $x$ is integer between $0$ and $n-1$ coprime with $n$. Returns $y$ such that $y^2 \bmod n = x$. If there are multiple such integers, only one of them is returned. If there are none, $-1$ is returned instead.
• ^ x y where $x$ and $y$ are integers between $0$ and $n-1$. Returns ${x^y \bmod n}$.

Find the factorisation of $n$ that is a product of between $2$ and $10$ distinct prime numbers, all of form $4x + 3$ for some integer $x$.

Because of technical issues, we restrict number of requests to $100$.

整数分解是困难的。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^2 \bmod n = x$ 的整数 $y$。若存在多个这样的整数，则仅返回其中一个；若不存在，则返回 $-1$。
• ^ x y：其中 $x$ 和 $y$ 是介于 $0$ 与 $n-1$ 之间的整数。返回 ${x^y \bmod n}$。

请对整数 $n$ 进行质因数分解，其中 $n$ 是 $2$ 至 $10$ 个互异素数的乘积，且每个素数均形如 $4x + 3$（$x$ 为某整数）。

由于技术限制，你最多只能发出 $100$ 次请求。

The only line contains a single integer $n$ ($21 \leq n \leq 2^{1024}$). It is guaranteed that $n$ is a product of between $2$ and $10$ distinct prime numbers, all of form $4x + 3$ for some integer $x$.

唯一一行包含一个整数 $n$（$21 \leq n \leq 2^{1024}$）。保证 $n$ 是 $2$ 到 $10$ 个互异素数的乘积，且每个素数均具有 $4x + 3$ 的形式（其中 $x$ 为某个整数）。

You can print as many queries as you wish, adhering to the time limit (see the Interaction section for more details).

When you think you know the answer, output a single line of form ! k p_1 p_2 ... p_k, where $k$ is the number of prime factors of $n$, and $p_i$ are the distinct prime factors. You may print the factors in any order.

Hacks input

For hacks, use the following format:.

The first should contain $k$ ($2 \leq k \leq 10$) — the number of prime factors of $n$.

The second should contain $k$ space separated integers $p_1, p_2, \dots, p_k$ ($21 \leq n \leq 2^{1024}$) — the prime factors of $n$. All prime factors have to be of form $4x + 3$ for some integer $x$. They all have to be distinct.

你可以输出任意数量的查询，只要满足时间限制（详见“交互”部分）。

当你认为自己已经得出答案时，请输出一行形如 ! k p_1 p_2 ... p_k 的答案，其中 $k$ 是 $n$ 的不同质因数的个数，$p_i$ 是 $n$ 的所有不同质因数。质因数的输出顺序可以任意。

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$（其中 $x$ 为某整数），且互不相同。

We start by reading the first line containing the integer $n = 21$. Then, we ask for:

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. Square root of $16$. The answer is $11$, as $(11 \cdot 11) \bmod 21 = 121 \bmod 21 = 16$. Note that the answer may as well be $10$.
6. Square root of $5$. There is no $x$ such that $x^2 \bmod 21 = 5$, so the output is $-1$.
7. $(6^{12}) \bmod 21 = 2176782336 \bmod 21 = 15$.

We conclude that our calculator is working, stop fooling around and realise that $21 = 3 \cdot 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^2 \bmod 21 = 5$ 的 $x$，因此输出 $-1$。
7. $(6^{12}) \bmod 21 = 2176782336 \bmod 21 = 15$。

我们由此确认计算器工作正常，停止胡闹，并意识到 $21 = 3 \cdot 7$。