Codeforces Global Round 6 |
---|
Закончено |
Пусть $$$a$$$ — матрица размера $$$r \times c$$$, в каждой ячейке которой записано положительное целое число (эти числа не обязательно различны). Строки матрицы пронумерованы от $$$1$$$ до $$$r$$$, а столбцы — от $$$1$$$ до $$$c$$$. Мы можем построить массив $$$b$$$, состоящий из $$$r + c$$$ целых чисел, следующим образом: для каждого $$$i \in [1, r]$$$ обозначим за $$$b_i$$$ наибольший общий делитель всех чисел в $$$i$$$-й строке, а для каждого $$$j \in [1, c]$$$ обозначим за $$$b_{r+j}$$$ наибольший общий делитель всех чисел в $$$j$$$-м столбце.
Назовем матрицу разнообразной, если все $$$r + c$$$ чисел $$$b_k$$$ ($$$k \in [1, r + c]$$$) попарно различны.
Назовем модулем матрицы максимальное число среди $$$b_k$$$.
Например, рассмотрим следующую матрицу:
Построим массив $$$b$$$:
Итак, $$$b = [1, 4, 2, 9, 7]$$$. Все значения в этом массиве различны, поэтому матрица является разнообразной. Модулем матрицы является число $$$9$$$.
Для заданных $$$r$$$ и $$$c$$$ найдите разнообразную матрицу с минимально возможным модулем. Если таких матриц несколько, найдите любую из них. Если решения нет, выведите единственное целое число $$$0$$$.
В единственной строке заданы два целых числа $$$r$$$ и $$$c$$$ ($$$1 \leq r,c \leq 500$$$) — количество строк и столбцов в требуемой матрице.
Если решения нет, выведите одно целое число $$$0$$$.
Иначе выведите $$$r$$$ строк. В $$$i$$$-й строке выведите $$$c$$$ целых чисел, разделенных пробелами, $$$j$$$-е из которых равно $$$a_{i,j}$$$ — положительному целому числу на пересечении $$$i$$$-й строки и $$$j$$$-го столбца в разнообразной матрице с минимальным модулем.
Для всех элементов матрицы должно соблюдаться условие $$$1 \leq a_{i,j} \leq 10^9$$$. Можно показать, что если решение существует, существует и решение, удовлетворяющее этим ограничениям (с тем же самым минимально возможным модулем).
2 2
4 12 2 9
1 1
0
В первом примере НОДы в строках равны $$$b_1 = 4$$$ и $$$b_2 = 1$$$, а НОДы в столбцах равны $$$b_3 = 2$$$ и $$$b_4 = 3$$$. Все НОДы различны, а максимальный из них равен $$$4$$$. Так как все НОДы должны быть различны и не могут быть меньше $$$1$$$, не существует разнообразных матриц $$$2 \times 2$$$ с модулем меньше $$$4$$$.
Во втором примере независимо от значения $$$a_{1,1}$$$ условие $$$b_1 = b_2$$$ будет всегда соблюдаться, поэтому разнообразных матриц не существует.
Название |
---|