You are given an image, that can be represented with a 2-d n by m grid of pixels. Each pixel of the image is either on or off, denoted by the characters "0" or "1", respectively. You would like to compress this image. You want to choose an integer k > 1 and split the image into k by k blocks. If n and m are not divisible by k, the image is padded with only zeros on the right and bottom so that they are divisible by k. Each pixel in each individual block must have the same value. The given image may not be compressible in its current state. Find the minimum number of pixels you need to toggle (after padding) in order for the image to be compressible for some k. More specifically, the steps are to first choose k, then the image is padded with zeros, then, we can toggle the pixels so it is compressible for this k. The image must be compressible in that state.


-----Input-----

The first line of input will contain two integers n, m (2 ≤ n, m ≤ 2 500), the dimensions of the image.

The next n lines of input will contain a binary string with exactly m characters, representing the image.


-----Output-----

Print a single integer, the minimum number of pixels needed to toggle to make the image compressible.


-----Example-----
Input
3 5
00100
10110
11001

Output
5



-----Note-----

We first choose k = 2.

The image is padded as follows: 

001000

101100

110010

000000



We can toggle the image to look as follows: 

001100

001100

000000

000000



We can see that this image is compressible for k = 2.

Difficulty: MEDIUM
Tags: Complete search
Skill types: Complete search

Starter code:

Solutions:
from sys import stdin

def run(n, m, pixels):
	ans = 1 << 30
	acc = [[0] * (m + 1) for _ in range(n + 1)]
	for i in range(n):
		for j in range(m):
			acc[i + 1][j + 1] = acc[i + 1][j] + int(pixels[i][j])
		for j in range(m):
			acc[i + 1][j + 1] += acc[i][j + 1]
	for k in range(2, max(n, m) + 1):
		(r, c) = ((n + k - 1) // k, (m + k - 1) // k)
		res = 0
		for i in range(r):
			for j in range(c):
				(x, y) = (i * k, j * k)
				(x2, y2) = (min(x + k - 1, n - 1), min(y + k - 1, m - 1))
				zero = acc[x2 + 1][y2 + 1] - acc[x][y2 + 1] - acc[x2 + 1][y] + acc[x][y]
				res += min(zero, k * k - zero)
		ans = min(ans, res)
	print(ans)

def main():
	(n, m) = [int(x) for x in stdin.readline().split()]
	pixels = []
	for i in range(n):
		pixels.append(stdin.readline().strip())
	run(n, m, pixels)

def __starting_point():
	import os
	if os.path.exists('tmp.in'):
		stdin = open('tmp.in')
	main()
__starting_point()


def debug(*a):
	return
	print('[DEBUG]', *a)
is_prime = [False, False] + [True] * (2600 - 2)
for i in range(2, 2600):
	if is_prime[i]:
		for j in range(i + i, 2600, i):
			is_prime[j] = False
(n, m) = map(int, input().split())
a = [None] * n
for i in range(n):
	a[i] = input()
b = [None] * (n + 1)
b[n] = [0] * (m + 1)
for i in range(n - 1, -1, -1):
	b[i] = [0] * (m + 1)
	for j in range(m - 1, -1, -1):
		b[i][j] = b[i + 1][j] + b[i][j + 1] - b[i + 1][j + 1] + int(a[i][j])
ans = None
for k in range(2, max(n, m) + 1):
	if is_prime[k]:
		kk = k * k
		aa = 0
		for i in range(0, n, k):
			for j in range(0, m, k):
				bb = b[i][j]
				if i + k < n:
					bb -= b[i + k][j]
				if j + k < m:
					bb -= b[i][j + k]
				if i + k < n and j + k < m:
					bb += b[i + k][j + k]
				aa += min(bb, kk - bb)
		if ans == None or aa < ans:
			ans = aa
print(ans)


from sys import stdin as fin

def check(x, y):
	if x < 0 or y < 0:
		return 0
	else:
		return d[x][y]

def check2(x, y):
	if x < 0 or y < 0:
		return 0
	else:
		return d[min(x, n - 1)][min(y, m - 1)]

def border(a, b):
	(d, m) = divmod(a, b)
	return b * (d + (m != 0))
(n, m) = map(int, fin.readline().split())
field = fin.readlines()
d = [[None] * m for i in range(n)]
d[0][0] = int(field[0][0])
for i in range(n):
	for j in range(m):
		d[i][j] = check(i - 1, j) + check(i, j - 1) - check(i - 1, j - 1) + int(field[i][j])
minv = float('inf')
for k in range(2, max(n, m)):
	cv = 0
	for i in range(k - 1, border(n, k), k):
		for j in range(k - 1, border(m, k), k):
			ccnt = check2(i, j) - check2(i - k, j) - check2(i, j - k) + check2(i - k, j - k)
			cv += min(ccnt, k ** 2 - ccnt)
	minv = min(minv, cv)
print(minv)
fin.close()


from sys import stdin as fin

def check(x, y):
	if x < 0 or y < 0:
		return 0
	else:
		return table2[x][y]
(n, m) = [int(x) for x in fin.readline().split()]
table = fin.readlines()
fin.close()
table2 = [[None] * m for _ in range(n)]
table2[0][0] = int(table[0][0])
for __ in range(1, m):
	table2[0][__] = int(table[0][__]) + table2[0][__ - 1]
for _ in range(1, n):
	table2[_][0] = int(table[_][0]) + table2[_ - 1][0]
	for __ in range(1, m):
		table2[_][__] = int(table[_][__]) + table2[_ - 1][__] + table2[_][__ - 1] - table2[_ - 1][__ - 1]
list_of_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163]
list_of_primes += [167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353]
list_of_primes += [359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569]
list_of_primes += [571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773]
list_of_primes += [787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013]
list_of_primes += [1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213]
list_of_primes += [1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429]
list_of_primes += [1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609]
list_of_primes += [1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831]
list_of_primes += [1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053]
list_of_primes += [2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273]
list_of_primes += [2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473, 2477]
minimum = float('inf')
for i in [x for x in list_of_primes if x <= max(n, m) + 1]:
	current = 0
	j = 0
	while j < n // i + (n % i != 0):
		k = 0
		while k < m // i + (m % i != 0):
			aofi = table2[min(j * i + i - 1, n - 1)][min(k * i + i - 1, m - 1)] - check(j * i - 1, min(k * i + i - 1, m - 1)) - check(min(j * i + i - 1, n - 1), k * i - 1) + check(min(j * i - 1, n - 1 - n % i), min(k * i - 1, m - 1 - m % i))
			current += min(aofi, i ** 2 - aofi)
			k += 1
		j += 1
	if current < minimum:
		minimum = current
print(minimum)