GCD_1 - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: kryptonix171
Tester: mexomerf
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

Find any N\times M grid containing integers between 2 and 10^9, such that every row and every column has GCD 1.

EXPLANATION:

There are many different constructions possible here.
One simple method is to use the fact that \gcd(x, x+1) = 1 for any integer x.
So, as long as there are at least two consecutive values in each row and each column, every GCD will definitely be 1.

For example, you can do something like

\begin{bmatrix} 2 & 3 & 4 & 5 & \ldots & M+1 \\ 3 & 4 & 5 & 6 & \ldots & M+2 \\ 4 & 5 & 6 & 7 & \ldots & M+3 \\ \vdots \\ N+1 & N+2 & N+3 & N+4 & \ldots & N+M \end{bmatrix}

It’s easy to see that every row and every column contains a pair of consecutive numbers, and so has GCD equal to 1.

There are, of course, many other constructions possible, and any valid one will be accepted.
However, do note that A_{i, j} \leq 10^9 must be satisfied: you can’t use integers that are too large.

TIME COMPLEXITY:

\mathcal{O}(N\cdot M) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n, m = map(int, input().split())
    for i in range(1, n+1):
        a = [i + j for j in range(1, m+1)]
        print(*a)
1 Like