CF1493F Enchanted Matrix

这是一个交互题。 存在一个大小为 $n \times m$ 的矩阵 $a$（有 $n$ 行 $m$ 列），你只知道 $n$ 和 $m$ 的数值。矩阵的行从上到下编号为 $1$ 到 $n$，列从左到右编号为 $1$ 到 $m$。第 $x$ 行第 $y$ 列的单元格记作 $(x, y)$。 你需要找出有多少对 $(r, c)$（$1 \le r \le n$，$1 \le c \le m$，$r$ 是 $n$ 的约数，$c$ 是 $m$ 的约数），使得如果将矩阵划分为若干个大小为 $r \times c$ 的矩形（每个矩形高 $r$ 行、宽 $c$ 列，每个单元格恰好属于一个矩形），那么所有这些矩形两两都完全相同。 你可以使用如下类型的询问： - ? $h$ $w$ $i_1$ $j_1$ $i_2$ $j_2$（$1 \le h \le n$，$1 \le w \le m$，$1 \le i_1, i_2 \le n$，$1 \le j_1, j_2 \le m$）——判断矩阵 $a$ 中两个不重叠的子矩形（高 $h$ 行、宽 $w$ 列）是否完全相同。第一个子矩形的左上角为 $(i_1, j_1)$，第二个子矩形的左上角为 $(i_2, j_2)$。如果两个子矩形有至少一个公共单元格，则视为重叠。如果你的询问坐标非法（例如超出矩阵边界）或两个子矩形重叠，你的解答将被判为错误。 你最多可以使用 $3 \cdot \left\lfloor \log_2{(n+m)} \right\rfloor$ 次询问。矩阵 $a$ 的所有元素在程序开始前已确定，并且不会因你的询问而改变。

第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 1000$），分别表示矩阵的行数和列数。

当你准备好输出答案时，输出一行，格式为感叹号（'!'）后跟答案，即满足条件的 $(r, c)$ 对数。输出后程序应立即结束。 交互说明 进行一次询问时，输出一行，格式为 "? $h$ $w$ $i_1$ $j_1$ $i_2$ $j_2$"，其中各整数分别为子矩形的高、宽及两个左上角的坐标。 每次询问后，读取一个整数 $t$（$t$ 为 $0$ 或 $1$）：如果两个子矩形完全相同，则 $t=1$，否则 $t=0$。 如果你的询问格式不正确，或者询问次数超过 $3 \cdot \left\lfloor \log_2{(n+m)} \right\rfloor$，你将被判为 Wrong Answer。 每次输出询问后请不要忘记输出换行并刷新输出缓冲区，否则会被判为 Idleness limit exceeded。具体做法如下： 6. C++ 使用 fflush(stdout) 或 cout.flush()； 7. Java 使用 System.out.flush()； 8. Pascal 使用 flush(output)； 9. Python 使用 stdout.flush()； 10. 其它语言请参考相关文档。 保证矩阵 $a$ 在交互过程中不会改变。 Hack 格式 Hack 时请使用如下格式。 第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 1000$），表示矩阵的行数和列数。 接下来 $n$ 行，每行包含 $m$ 个整数，表示矩阵 $a$ 的元素。所有元素均为 $1$ 到 $n \cdot m$ 之间的整数。

在示例测试中，$3 \times 4$ 的矩阵 $a$ 如下： ``` 1 2 1 2 3 3 3 3 2 1 2 1 ``` 由 ChatGPT 4.1 翻译