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

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

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

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

С одной стороны, если какой-то отрезок вида [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;
}