Очень легко привести входные данные в несжатый вид (входные данные были даны в сжатом формате для того, чтобы сделать ограничения больше, но при этом менее зависимыми от времени на чтение данных).

Авторское решение выглядит следующим образом:

Пусть 𝑥
— ответ на задачу, и изначально он равен 𝑛
. Переберем все строки матрицы и посчитаем длины максимальных по включению отрезков состоящих только из нулей или только из единиц. Пусть длина текущего отрезка равна 𝑙𝑒𝑛
. Тогда присвоим 𝑥:=𝑔𝑐𝑑(𝑥,𝑙𝑒𝑛)
, где 𝑔𝑐𝑑
— функция, считающая наибольший общий делитель. Затем сделаем тоже самое для столбцов матрицы и выведем ответ.

Как доказать, что это решение работает?

С одной стороны, если какой-то отрезок вида [1+𝑙𝑥,1+(𝑙+1)𝑥]
, где 𝑙
— это значение из отрезка [0;𝑛𝑥−1]
, содержит различные цифры, то тогда мы не сможем сжать заданную матрицу.

С другой стороны, если предыдущее условие верно, то мы можем сжать каждую строку по следующему алгоритму: откусим первые 𝑥
символов строки и сожмем оставшуюся строку рекурсивно. После такого сжатия мы получим матрицу размера 𝑛×𝑛𝑥
. И из-за первого условия мы можем сжать оставшуюся матрицу снова при помощи этого алгоритма, если мы применим его к столбцам, а не строкам.

#include <bits/stdc++.h>

using namespace std;

const int N = 5200;

int n;
bool a[N][N];

void parse_char(int x, int y, char c) {
int num = -1;
if (isdigit(c)) {
num = c - '0';
} else {
num = c - 'A' + 10;
}
for (int i = 0; i < 4; ++i) {
a[x][y + 3 - i] = num & 1;
num >>= 1;
}
}

int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif


scanf("%d", &n);
char buf[N];
for (int i = 0; i < n; ++i) {
scanf("%s", buf);
for (int j = 0; j < n / 4; ++j) {
parse_char(i, j * 4, buf[j]);
}
}

int g = n;

for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
int k = j;
while (k < n && a[i][k] == a[i][j]) ++k;
g = __gcd(g, k - j);
j = k - 1;
}
}

for (int j = 0; j < n; ++j) {
for (int i = 0; i < n; ++i) {
int k = i;
while (k < n && a[k][j] == a[i][j]) ++k;
g = __gcd(g, k - i);
i = k - 1;
}
}

cout << g << endl;

return 0;
}