Given a matrix you need to find the submatrix with the largest number of elements, where the GCD (Greatest Common Divisor) of its elements is greater than one. A submatrix of the matrix is a sub-section composed of contiguous rows and columns of the original matrix.

Input
Two numbers n,m in the first line. Followed by n lines with m numbers in each line.

Constraints  

1<=N,M<=200

1<=numbers<=10000

Output
Just a largest area where GCD is greater than 1.

Sample Input  

3 3
2 6 8
4 8 3
6 9 4

Sample Output  

4

If you observe the following submatrix:  

2 6  
4 8  

The GCD is 2.
There is no matrix larger than this with a GCD > 1.

Source: hackerrank | Difficulty: MEDIUM_HARD
Tags: Number theory


Solutions:
from sys import stderr

def main():
	print(solve(readcase()))

def readcase():
	(n, m) = readints()
	mtx = []
	for _ in range(n):
		mtx.append(readints())
		assert len(mtx[0]) == m
	return mtx

def readints():
	return [int(f) for f in input().split()]

def solve(m):
	best = 0
	(nrows, ncols) = (len(m), len(m[0]))
	for irow in range(nrows):
		for icol in range(ncols):
			upperrow = [m[irow][icol]] * (ncols - icol)
			cur = m[irow][icol]
			for jrow in range(irow, nrows):
				prev = m[irow][icol]
				goodcols = 0
				for jcol in range(icol, ncols):
					prev = gcd(prev, gcd(upperrow[jcol - icol], m[jrow][jcol]))
					if prev == 1:
						upperrow[jcol - icol:] = [1] * (ncols - jcol)
						break
					goodcols += 1
					upperrow[jcol - icol] = prev
				if best >= (nrows - irow) * goodcols:
					break
				best = max(best, (jrow - irow + 1) * goodcols)
	return best

def gcd(a, b):
	(a, b) = (max(a, b), min(a, b))
	while b != 0:
		(a, b) = (b, a % b)
	return a
main()


def gcd(a, b):
	if b:
		return gcd(b, a % b)
	else:
		return a

def subvectorGCDs(row):
	hash = {}
	for (start, a) in enumerate(row):
		current_gcd = a
		for end in range(start, len(row)):
			b = row[end]
			current_gcd = gcd(b, current_gcd)
			if current_gcd == 1:
				break
			else:
				hash[start, end] = current_gcd
	return hash

def LNCPM(M):
	partial_row_GCDs = [subvectorGCDs(row) for row in M]
	num_rows = len(partial_row_GCDs)
	max_area = 0
	for (r, row) in enumerate(partial_row_GCDs):
		for (a, b) in row:
			if (num_rows - r + 1) * (b - a + 1) < max_area:
				continue
			(area, _) = grow(partial_row_GCDs, (a, b), r)
			if area > max_area:
				max_area = area
	return max_area

def submatrix(r1, r2, c1, c2, matrix):
	return [[matrix[i][j] for j in range(c1, c2 + 1)] for i in range(r1, r2 + 1)]

def matrixToString(M):
	return '\n'.join((' '.join(map(str, row)) for row in M))

def grow(pr_gcds, cor, row):
	area = 0
	current_gcd = 0
	(a, b) = cor
	while row < len(pr_gcds) and (a, b) in pr_gcds[row]:
		current_gcd = gcd(pr_gcds[row][a, b], current_gcd)
		if current_gcd == 1:
			return (area, row - 1)
		else:
			area += b - a + 1
			row += 1
	return (area, row - 1)
(rows, columns) = map(int, input().split())
matrix = [[int(k) for k in input().split()] for row in range(rows)]
print(LNCPM(matrix))


from sys import stderr

def main():
	print(solve(readcase()))

def readcase():
	(n, m) = readints()
	mtx = []
	for _ in range(n):
		mtx.append(readints())
		assert len(mtx[0]) == m
	return mtx

def readints():
	return [int(f) for f in input().split()]

def solve(m):
	best = 0
	(nrows, ncols) = (len(m), len(m[0]))
	for irow in range(nrows):
		for icol in range(ncols):
			upperrow = [m[irow][icol]] * (ncols - icol)
			cur = m[irow][icol]
			for jrow in range(irow, nrows):
				prev = m[irow][icol]
				goodcols = 0
				for jcol in range(icol, ncols):
					prev = gcd(prev, gcd(upperrow[jcol - icol], m[jrow][jcol]))
					if prev == 1:
						upperrow[jcol - icol:] = [1] * (ncols - jcol)
						break
					goodcols += 1
					upperrow[jcol - icol] = prev
				if best >= (nrows - irow) * goodcols:
					break
				best = max(best, (jrow - irow + 1) * goodcols)
	return best

def gcd(a, b):
	(a, b) = (max(a, b), min(a, b))
	while b != 0:
		(a, b) = (b, a % b)
	return a
main()


from sys import stderr

def main():
	print(solve(readcase()))

def readcase():
	(n, m) = readints()
	mtx = []
	for _ in range(n):
		mtx.append(readints())
		assert len(mtx[0]) == m
	return mtx

def readints():
	return [int(f) for f in input().split()]

def solve(m):
	best = 0
	(nrows, ncols) = (len(m), len(m[0]))
	for irow in range(nrows):
		for icol in range(ncols):
			upperrow = [m[irow][icol]] * (ncols - icol)
			cur = m[irow][icol]
			for jrow in range(irow, nrows):
				prev = m[irow][icol]
				goodcols = 0
				for jcol in range(icol, ncols):
					prev = gcd(prev, gcd(upperrow[jcol - icol], m[jrow][jcol]))
					if prev == 1:
						upperrow[jcol - icol:] = [1] * (ncols - jcol)
						break
					goodcols += 1
					upperrow[jcol - icol] = prev
				if best >= (nrows - irow) * goodcols:
					break
				best = max(best, (jrow - irow + 1) * goodcols)
	return best

def gcd(a, b):
	(a, b) = (max(a, b), min(a, b))
	while b != 0:
		(a, b) = (b, a % b)
	return a
main()


from sys import stderr

def main():
	print(solve(readcase()))

def readcase():
	(n, m) = readints()
	mtx = []
	for _ in range(n):
		mtx.append(readints())
		assert len(mtx[0]) == m
	return mtx

def readints():
	return [int(f) for f in input().split()]

def solve(m):
	best = 0
	(nrows, ncols) = (len(m), len(m[0]))
	for irow in range(nrows):
		for icol in range(ncols):
			upperrow = [m[irow][icol]] * (ncols - icol)
			cur = m[irow][icol]
			for jrow in range(irow, nrows):
				prev = m[irow][icol]
				goodcols = 0
				for jcol in range(icol, ncols):
					prev = gcd(prev, gcd(upperrow[jcol - icol], m[jrow][jcol]))
					if prev == 1:
						upperrow[jcol - icol:] = [1] * (ncols - jcol)
						break
					goodcols += 1
					upperrow[jcol - icol] = prev
				if best >= (nrows - irow) * goodcols:
					break
				best = max(best, (jrow - irow + 1) * goodcols)
	return best

def gcd(a, b):
	(a, b) = (max(a, b), min(a, b))
	while b != 0:
		(a, b) = (b, a % b)
	return a
main()