← 返回题目列表

Codeforces · 1107/D

D. 压缩

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

给定一个二进制矩阵 $$$A$$$,大小为 $$$n \times n$$$。让我们将给定矩阵的 $$$x$$$ 压缩表示为大小为 $$$\frac{n}{x} \times \frac{n}{x}$$$ 的矩阵 $$$x$$$,这样对于每个 $$$i \in [1, n], j \in [1, n]$$$,条件 $$$A[i][j] = B[\lceil \frac{i}{x} \rceil][\lceil \frac{j}{x} \rceil]$$$ 满足。

显然,$$$x$$$-只有当$$$x$$$整除$$$n$$$时才可能进行压缩,但这个条件还不够。例如,以下大小为 $$$2 \times 2$$$ 的矩阵没有任何 $$$2$$$ 压缩:

$$$01$$$

$$$10$$$

对于给定的矩阵 $$$A$$$,找到最大值 $$$x$$$,使得可以对该矩阵进行 $$$x$$$ 压缩。

请注意,输入以压缩形式给出。但即使它是压缩的,你最好使用快速输入。

输入

第一行包含一个数字 $$$n$$$ ($$$4 \le n \le 5200$$$) — 矩阵 $$$A$$$ 中的行数和列数。保证 $$$n$$$ 能被 $$$4$$$ 整除。

那么矩阵的表示如下。 $$$n$$$ 接下来的每一行都包含 $$$\frac{n}{4}$$$ 一位十六进制数字(也就是说,这些数字可以表示为从 $$$0$$$ 到 $$$9$$$ 的数字,也可以表示为从 $$$A$$$ 到 $$$F$$$ 的大写拉丁字母)。每个数字的二进制表示表示相应行中矩阵的下一个 $$$4$$$ 元素。例如,如果给定数字$$$B$$$,则对应的元素为1011,如果给定数字$$$5$$$,则对应的元素为0101。

元素不以空格分隔。

输出

打印一个数字:最大 $$$x$$$,以便可以对给定矩阵进行 $$$x$$$ 压缩。

示例

输入 #1

8
E7
E7
E7
00
00
E7
E7
E7

输出 #1

1

输入 #2

4
7
F
F
F

输出 #2

1

注意

第一个示例对应于矩阵:

$$$11100111$$$

$$$11100111$$$

$$$11100111$$$

$$$00000000$$$

$$$00000000$$$

$$$11100111$$$

$$$11100111$$$

$$$11100111$$$

很容易看出这个例子的答案是$$$1$$$。