306884: CF1266C. Diverse Matrix

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Diverse Matrix

题意翻译

### 题目描述 对于一个r行c列的矩阵,我们可以求出它每一行,每一列的最大公约数(共r+c个数)。 输入r,c。要求输出一个矩阵,满足这r+c个数不同,且这r+c个数的最大值最小。 ### 输入格式 输入一行两个整数,分别为r,c。(1≤r,c≤500) ### 输出格式 如果无解输出0,否则输出你构造的r行c列的矩阵,要求矩阵中的每个元素满足1≤a≤1e9 。

题目描述

Let $ a $ be a matrix of size $ r \times c $ containing positive integers, not necessarily distinct. Rows of the matrix are numbered from $ 1 $ to $ r $ , columns are numbered from $ 1 $ to $ c $ . We can construct an array $ b $ consisting of $ r + c $ integers as follows: for each $ i \in [1, r] $ , let $ b_i $ be the greatest common divisor of integers in the $ i $ -th row, and for each $ j \in [1, c] $ let $ b_{r+j} $ be the greatest common divisor of integers in the $ j $ -th column. We call the matrix diverse if all $ r + c $ numbers $ b_k $ ( $ k \in [1, r + c] $ ) are pairwise distinct. The magnitude of a matrix equals to the maximum of $ b_k $ . For example, suppose we have the following matrix: $ \begin{pmatrix} 2 & 9 & 7\\ 4 & 144 & 84 \end{pmatrix} $ We construct the array $ b $ : 1. $ b_1 $ is the greatest common divisor of $ 2 $ , $ 9 $ , and $ 7 $ , that is $ 1 $ ; 2. $ b_2 $ is the greatest common divisor of $ 4 $ , $ 144 $ , and $ 84 $ , that is $ 4 $ ; 3. $ b_3 $ is the greatest common divisor of $ 2 $ and $ 4 $ , that is $ 2 $ ; 4. $ b_4 $ is the greatest common divisor of $ 9 $ and $ 144 $ , that is $ 9 $ ; 5. $ b_5 $ is the greatest common divisor of $ 7 $ and $ 84 $ , that is $ 7 $ . So $ b = [1, 4, 2, 9, 7] $ . All values in this array are distinct, so the matrix is diverse. The magnitude is equal to $ 9 $ . For a given $ r $ and $ c $ , find a diverse matrix that minimises the magnitude. If there are multiple solutions, you may output any of them. If there are no solutions, output a single integer $ 0 $ .

输入输出格式

输入格式


The only line in the input contains two space separated integers $ r $ and $ c $ ( $ 1 \leq r,c \leq 500 $ ) — the number of rows and the number of columns of the matrix to be found.

输出格式


If there is no solution, output a single integer $ 0 $ . Otherwise, output $ r $ rows. The $ i $ -th of them should contain $ c $ space-separated integers, the $ j $ -th of which is $ a_{i,j} $ — the positive integer in the $ i $ -th row and $ j $ -th column of a diverse matrix minimizing the magnitude. Furthermore, it must hold that $ 1 \leq a_{i,j} \leq 10^9 $ . It can be shown that if a solution exists, there is also a solution with this additional constraint (still having minimum possible magnitude).

输入输出样例

输入样例 #1

2 2

输出样例 #1

4 12
2 9

输入样例 #2

1 1

输出样例 #2

0

说明

In the first example, the GCDs of rows are $ b_1 = 4 $ and $ b_2 = 1 $ , and the GCDs of columns are $ b_3 = 2 $ and $ b_4 = 3 $ . All GCDs are pairwise distinct and the maximum of them is $ 4 $ . Since the GCDs have to be distinct and at least $ 1 $ , it is clear that there are no diverse matrices of size $ 2 \times 2 $ with magnitude smaller than $ 4 $ . In the second example, no matter what $ a_{1,1} $ is, $ b_1 = b_2 $ will always hold, so there are no diverse matrices.

Input

题意翻译

### 题目描述 对于一个r行c列的矩阵,我们可以求出它每一行,每一列的最大公约数(共r+c个数)。 输入r,c。要求输出一个矩阵,满足这r+c个数不同,且这r+c个数的最大值最小。 ### 输入格式 输入一行两个整数,分别为r,c。(1≤r,c≤500) ### 输出格式 如果无解输出0,否则输出你构造的r行c列的矩阵,要求矩阵中的每个元素满足1≤a≤1e9 。

加入题单

上一题 下一题 算法标签: