Anas is playing an amazing game on a grid with $N$ rows and $M$ columns. The rows are numbered $1$ through $N$ from top to bottom and the columns are numbered $1$ through $M$ from left to right.
Anas wants to destroy this grid. To do that, he wants to send two heroes from the top left cell to the bottom right cell:
- The first hero visits cells in row-major order: $(1,1) \rightarrow (1,2) \rightarrow \ldots \rightarrow (1,M) \rightarrow (2,1) \rightarrow (2,2) \rightarrow \ldots \rightarrow (2,M) \rightarrow \ldots \rightarrow (N,M)$.
- The second hero visits cells in column-major order: $(1,1) \rightarrow (2,1) \rightarrow \ldots \rightarrow (N,1) \rightarrow (1,2) \rightarrow (2,2) \rightarrow \ldots \rightarrow (N,2) \rightarrow \ldots \rightarrow (N,M)$.
We know that each hero destroys the first cell he visits, rests in the next $K$ cells he visits without destroying them, then destroys the next cell he visits, rests in the next $K$ cells, destroys the next cell, and so on until he reaches (and rests in or destroys) the last cell he visits.
Anas does not know the value of $K$. Therefore, for each value of $K$ between $0$ and $N \cdot M - 1$ inclusive, he wants to calculate the number of cells that will be destroyed by at least one hero. Can you help him?

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first and only line of each test case contains two space-separated integers $N$ and $M$.

-----Output-----
For each test case, print a single line containing $N \cdot M$ space-separated integers as described above.

-----Constraints-----
- $1 \le T \le 100$
- $2 \le N, M \le 1,000$
- the sum of $N \cdot M$ over all test cases does not exceed $2 \cdot 10^6$

-----Subtasks-----
Subtask #1 (30 points):
- $2 \le N, M \le 50$
- the sum of $N \cdot M$ over all test cases does not exceed $5,000$
Subtask #2 (70 points): original constraints

-----Example Input-----
1
2 3

-----Example Output-----
6 4 3 3 2 1

-----Explanation-----
Example case 1:
- $K = 0$: All cells will be destroyed by the heroes.
- $K = 1$: The first hero will destroy the cells $[(1,1), (1,3), (2,2)]$, while the second one will destroy the cells $[(1,1), (1,2), (1,3)]$.
- $K = 2$: The first hero will destroy the cells $[(1,1), (2,1)]$, while the second one will destroy the cells $[(1,1), (2,2)]$.
- $K = 3$: The first hero will destroy the cells $[(1,1), (2,2)]$, while the second one will destroy the cells $[(1,1), (1,3)]$.
- $K = 4$: The first hero will destroy the cells $[(1,1), (2,3)]$ and the second one will also destroy the cells $[(1,1), (2,3)]$.
- $K = 5$ : The first hero will destroy the cell $(1,1)$ and the second one will also destroy the cell $(1,1)$.

Difficulty: HARD
Tags: Number theory

Mathematics

Starter code:

Solutions:
for x in range(int(input())):
	(n, m) = map(int, input().split())
	y = n * m
	l = []
	for x in range(n * m):
		p = x + 1
		if y % p == 0:
			ans = 2 * (y // p)
		else:
			ans = 2 * (y // p + 1)
		mu = 0
		while mu < y:
			n1 = mu // m
			m1 = mu % m
			y2 = m1 * n + n1
			if y2 % (x + 1) == 0:
				ans -= 1
			mu += x + 1
		print(ans, end=' ')
	print('')


from math import ceil
for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	l = [str(n * m)]
	for i in range(1, n * m):
		c = 2 * ceil(n * m / (i + 1))
		for k in range(0, n * m, i + 1):
			r = k % m
			q = k // m
			if (r * n + q) % (i + 1) == 0:
				c -= 1
		l.append(str(c))
	print(' '.join(l))


for x in range(int(input())):
	(n, m) = map(int, input().split())
	y = n * m
	for x in range(n * m):
		a = 1
		b = 1
		d = {(1, 1): 1}
		count = 1
		if x == 0:
			print(n * m, end=' ')
			continue
		while True:
			b = b + x + 1
			if b > m:
				u = b - m
				if u % m == 0:
					a = a + u // m
					b = m
				else:
					a = a + u // m + 1
					b = u % m
			if a > n:
				break
			else:
				d[a, b] = 1
				count += 1
		a = 1
		b = 1
		while True:
			a = a + x + 1
			if a > n:
				u = a - n
				if u % n == 0:
					b = b + u // n
					a = n
				else:
					b = b + u // n + 1
					a = u % n
			if b > m:
				break
			elif (a, b) not in d.keys():
				count += 1
		print(count, end=' ')
	print('')


t = int(input(''))
for v in range(t):
	a = input('').split(' ')
	n = int(a[0])
	m = int(a[1])
	ans = [0] * (n * m)
	for k in range(0, n * m, 1):
		su = 2 * ((n * m - 1) // (k + 1) + 1)
		g = 0
		while g < n * m:
			j = g % m
			i = g // m
			if (j * n + i) % (k + 1) == 0:
				su = su - 1
			g = g + (k + 1)
		print(su, end=' ')
	print('')


def find_destroyed_cells(cell_advance, n, m, k):
	row = 1
	col = 1
	destroyed_cells = {(1, 1)}
	while True:
		(row, col) = cell_advance(row, col, n, m, k)
		if row <= n and col <= m:
			destroyed_cells.add((row, col))
		else:
			break
	return destroyed_cells

def cell_advance_hero1(row, col, n, m, k):
	return (row + (col + k) // m, (col + k) % m + 1)

def cell_advance_hero2(row, col, n, m, k):
	return ((row + k) % n + 1, col + (row + k) // n)

def main():
	t = int(input())
	for _ in range(t):
		(n, m) = [int(s) for s in input().split(' ')]
		counts = []
		for k in range(n * m):
			cells_h1 = find_destroyed_cells(cell_advance_hero1, n, m, k)
			cells_h2 = find_destroyed_cells(cell_advance_hero2, n, m, k)
			destroyed = len(cells_h1) + len(cells_h2) - len(cells_h1 & cells_h2)
			counts.append(destroyed)
		print(' '.join([str(c) for c in counts]))
main()


t = int(input())
for tc in range(t):
	(n, m) = map(int, input().split())
	s = n * m
	x = []
	y = []
	z = []
	a = []
	print(n * m, end=' ')
	for i in range(1, n + 1):
		for j in range(1, m + 1):
			x.append([i, j])
	for j in range(1, m + 1):
		for i in range(1, n + 1):
			y.append([i, j])
	for k in range(1, m * n):
		a = []
		z = []
		for i in range(0, n * m, k + 1):
			z.append(x[i])
		for j in range(0, n * m, k + 1):
			z.append(y[j])
		for i in z:
			if i not in a:
				a.append(i)
		print(len(a), end=' ')
	print()


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	for k in range(n * m):
		s = ''
		t = ''
		for i in range(n * m):
			s += '0'
		i = 0
		while i < len(s):
			s = s[:i] + '1' + s[i + 1:]
			i += k + 1
		i = 0
		for i in range(n):
			while i < len(s):
				t += s[i]
				i += n
		i = 0
		while i < len(t):
			t = t[:i] + '1' + t[i + 1:]
			i += k + 1
		print(t.count('1'), ' ', end='')


def findmax(r, c, k):
	count = 0
	if r * c % (k + 1) == 0:
		summ = 2 * (r * c // (k + 1))
	else:
		summ = 2 * (r * c // (k + 1) + 1)
	(x, y, n) = (0, 0, 0)
	while 1:
		x = (k + 1) * n // c
		y = (k + 1) * n % c
		if y >= c or x >= r:
			break
		elif (r * y + x) % (k + 1) == 0:
			count += 1
		n += 1
	summ -= count
	print(summ, end=' ')
t = int(input())
while t > 0:
	(r, c) = input().split()
	(r, c) = (int(r), int(c))
	for k in range(r * c):
		findmax(r, c, k)
	t -= 1


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	print(n * m, end=' ')
	for k in range(1, n * m):
		ans = (n * m - 1) // (k + 1) + 1
		for j in range(k + 1, n * m, k + 1):
			q = j // m + j % m * n
			if q % (k + 1) != 0:
				ans += 1
		print(ans, end=' ')


T = int(input())
for t in range(T):
	(N, M) = list(map(int, input().split()))
	print(N * M, end=' ')
	for k in range(1, N * M):
		ans = 2 * (1 + (N * M - 1) // (k + 1))
		mult = 0
		while mult < N * M:
			n = mult // M
			m = mult % M
			y2 = m * N + n
			if y2 % (k + 1) == 0:
				ans -= 1
			mult += k + 1
		print(ans, end=' ')
	print()


t = int(input())
while t > 0:
	t -= 1
	(n, m) = input().split()
	n = int(n)
	m = int(m)
	b = []
	for i in range(m):
		for j in range(n):
			b.append(i + 1 + m * j)
	k = [n * m]
	for i in range(1, n * m):
		s = set()
		for j in range(1, n * m + 1, i + 1):
			s.add(j)
			s.add(b[j - 1])
		k.append(len(s))
	k = ' '.join((str(k[x]) for x in range(len(k))))
	print(k)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	lim = n * m + 1
	k = lim - 1
	lst = [int(num) for num in range(1, lim)]
	lst2 = []
	for val in range(1, m + 1):
		for val2 in range(n):
			lst2.append(val + m * val2)
	for val_k in range(k):
		lst_k = []
		for index in range(0, lim - 1, val_k + 1):
			lst_k.append(lst[index])
			lst_k.append(lst2[index])
		print(len(set(lst_k)), end=' ')
	print()


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

def find_factors(N):
	factors = []
	factors2 = []
	for i in range(1, int(N ** 0.5) + 1):
		if N % i == 0:
			factors += [i]
			factors2 += [N // i]
	if factors[-1] == factors2[-1]:
		return factors + factors2[:-1]
	else:
		return factors + factors2

def find(M, N):
	ans = [0] * (M * N)
	for x in range(N):
		for y in range(M):
			if x == 0 and y == 0:
				ans[0] += 1
				continue
			N_1 = x * M + y
			N_2 = y * N + x
			G = gcd(N_1, N_2)
			check = find_factors(G)
			for c in check:
				ans[c - 1] += 1
	real_ans = [0] * (M * N)
	real_ans[0] = M * N
	for K in range(1, M * N):
		temp = (1 + (M * N - 1) // (K + 1)) * 2 - ans[K] - 1
		real_ans[K] = temp
	return real_ans
for _ in range(int(input())):
	(M, N) = list(map(int, input().strip().split(' ')))
	Ans = find(M, N)
	print(*Ans)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	l = n * m
	print(*(len(set(range(0, l, k)) | {i % n * m + i // n for i in range(0, l, k)}) for k in range(1, l + 1)))


mod = 1000000007
ii = lambda : int(input())
si = lambda : input()
dgl = lambda : list(map(int, input()))
f = lambda : map(int, input().split())
il = lambda : list(map(int, input().split()))
it = lambda : tuple(map(int, input().split()))
ls = lambda : list(input())
t = ii()
for _ in range(t):
	(n, m) = f()
	l = n * m
	for i in range(1, l + 1):
		s1 = set((j for j in range(0, n * m, i)))
		s2 = set((j % n * m + j // n for j in range(0, n * m, i)))
		print(len(s1 | s2), end=' ')
	print()


ans = [[False for _ in range(1001)] for _ in range(1001)]
for _ in range(int(input())):
	(r, c) = map(int, input().split())
	count = 0
	for i in range(0, r * c):
		val = 0
		for x in range(0, r * c, i + 1):
			a = x // r
			b = x % r
			ans[a][b] = True
			a = x % c
			b = x // c
			ans[a][b] = True
		for x in range(0, r * c, i + 1):
			a = x // r
			b = x % r
			if ans[a][b] == True:
				ans[a][b] = False
				val += 1
			a = x % c
			b = x // c
			if ans[a][b] == True:
				ans[a][b] = False
				val += 1
		print(val, end=' ')


for x in range(int(input())):
	(n, m) = map(int, input().split())
	y = n * m
	l = [(1, 1)]
	for x in range(n * m):
		l = [(1, 1)]
		a = 1
		b = 1
		if x == 0:
			print(n * m, end=' ')
			continue
		while True:
			b = b + x + 1
			if b > m:
				u = b - m
				if u % m == 0:
					a = a + u // m
					b = m
				else:
					a = a + u // m + 1
					b = u % m
			if a > n:
				break
			else:
				l.append((a, b))
		a = 1
		b = 1
		while True:
			a = a + x + 1
			if a > n:
				u = a - n
				if u % n == 0:
					b = b + u // n
					a = n
				else:
					b = b + u // n + 1
					a = u % n
			if b > m:
				break
			else:
				l.append((a, b))
		print(len(set(l)), end=' ')
	print('')


try:
	t = int(input())
	for i in range(t):
		c = {}
		r = []
		(n, m) = map(int, input().split())
		l = [i for i in range(1, m * n + 1)]
		count = 0
		sum1 = 0
		for j in range(0, n * m, m):
			c[count] = l[j:j + m]
			count = count + 1
		i = 0
		x = len(c[0])
		while i < x:
			for k in c.values():
				r.append(k[i])
			i = i + 1
		for k in range(1, m * n + 1):
			p1 = l[::k]
			p2 = r[::k]
			print(len(set(p1 + p2)), end=' ')
except Exception as e:
	pass


ans = set()
for _ in range(int(input())):
	(r, c) = map(int, input().split())
	count = 0
	for i in range(0, r * c):
		ans.clear()
		for x in range(0, r * c, i + 1):
			a = x // r
			b = x % r
			ans.add((a, b))
			a = x % c
			b = x // c
			ans.add((a, b))
		print(len(ans), end=' ')


def destcell(r, c):
	t = []
	for i in range(c):
		for j in range(r):
			t.append(i + j * c)
	for i in range(0, r * c):
		d = set()
		for j in range(0, r * c, i + 1):
			d.add(j)
			d.add(t[j])
		print(len(d), end=' ')
	print()
t = int(input())
while t:
	t -= 1
	(r, c) = map(int, input().split())
	destcell(r, c)


t = int(input())
l = []
for i in range(0, t):
	ele = list(map(int, input().split()))
	l.append(ele)
for i in range(0, t):
	n = l[i][0]
	m = l[i][1]
	f1 = []
	f2 = []
	for j in range(1, n + 1):
		for h in range(1, m + 1):
			f1.append((j, h))
	for j in range(1, m + 1):
		for h in range(1, n + 1):
			f2.append((h, j))
	for k in range(0, n * m):
		if k == 0:
			print(n * m, end=' ')
		else:
			y = []
			z = []
			e = 0
			while e * (k + 1) < n * m:
				y.append(f1[e * (k + 1)])
				z.append(f2[e * (k + 1)])
				e = e + 1
			for x in z:
				if x not in y:
					y.append(x)
			print(len(y), end=' ')


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	k = n * m
	transpose = []
	for _i in range(m):
		for _j in range(n):
			transpose.append(_i + _j * m)
	for i in range(0, n * m):
		done = set()
		for j in range(0, n * m, i + 1):
			done.add(j)
			done.add(transpose[j])
		print(len(done), end=' ')
	print()


for _ in range(int(input())):
	(r, c) = map(int, input().split())
	count = 0
	for i in range(0, r * c):
		ans = list()
		for x in range(0, r * c, i + 1):
			a = x // r
			b = x % r
			ans.append((a, b))
			a = x % c
			b = x // c
			ans.append((a, b))
		print(len(set(ans)), end=' ')


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	ht = {i: 0 for i in range(n * m)}
	ht[0] = n * m
	transpose = []
	for i in range(m):
		for j in range(n):
			transpose.append(i + j * m)
	k = 0
	while k < n * m:
		g = set()
		for i in range(0, n * m, k + 1):
			g.add(i)
			g.add(transpose[i])
		ht[k] = len(g)
		k += 1
	for key in ht.keys():
		print(ht[key], end=' ')
	print()


from itertools import chain
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	l = n * m
	print(*(len(set(chain.from_iterable(((i, i % n * m + i // n) for i in range(0, l, k))))) for k in range(1, l + 1)))


def destroy_cells(N, M):
	print(N * M, end=' ')
	for k in range(1, N * M - 1):
		(row, col, i, j) = (0, 0, 0, 0)
		positions = [(0, 0)]
		while row < N or col < M:
			j = j + k + 1
			if j >= M:
				row += j // M
			if row < N:
				j = j % M
				positions.append((row, j))
			i = i + k + 1
			if i >= N:
				col += i // N
			if col < M:
				i = i % N
				positions.append((i, col))
		positions = set(positions)
		print(len(positions), end=' ')
	print(1)
test = int(input())
for i in range(test):
	(N, M) = map(int, input().split())
	destroy_cells(N, M)


t = int(input())
while t > 0:
	ans = []
	(n, m) = list(map(int, input().split()))
	temp = []
	for k in range(0, n * m):
		myset1 = set()
		myset2 = set()
		if k == 0:
			ans.append(n * m)
		elif k == n * m - 1:
			ans.append(1)
		else:
			for j in range(1, m + 1):
				i = j
				while i <= n * m:
					temp.append(i)
					i += m
			i = 1
			while i <= n * m:
				myset1.add(i)
				i = i + k + 1
			i = 0
			while i <= n * m - 1:
				myset2.add(temp[i])
				i = i + k + 1
			current = list(myset1.union(myset2))
			ans.append(len(current))
	print(*ans)
	t -= 1


for i in range(int(input())):
	(n, m) = map(int, input().split())
	ans = [0] * (n * m)
	for k in range(0, n * m):
		ans[k] = n * m // (k + 1)
		count = 0
		if n * m % (k + 1) != 0:
			ans[k] += 1
		ans[k] = ans[k] * 2
		for j in range(1, n * m + 1, k + 1):
			y = j // m
			if j % m == 0:
				x = m
				y -= 1
			else:
				x = j % m
			if ((x - 1) * n + y) % (k + 1) == 0:
				count += 1
		ans[k] -= count
	print(*ans)