P7243 Greatest Common Divisor

  “Seeking the greatest common divisor is the true meaning of people’s democracy. ……”   In early autumn, sunlight dripped from the branches. It was soft, splashing onto the classroom window frame, moistening the cheeks of the girls reading aloud in the morning.   “A-Ling, A-Ling,” Tianyi bent down, her twin braids hanging over the edge of the upright textbook. “What is our greatest common divisor?”   “It must be not small,” she quietly pinched Tianyi’s forearm with her left hand. “For example, there is a common factor, called ‘you like me, and I like you too’.”

On the contrary, social circles come in all kinds of shapes, and the common divisors are pitifully small. It seems hard to keep one’s own personality, and thus one becomes a boring person. Now abstract interpersonal relationships into an $n \times m$ rectangle. Each person’s initial personality is $a_{i,j}$. Starting from the second day, each person will build relationships with the four people up, down, left, and right (if they exist), and their personality becomes the greatest common divisor of their own personality yesterday and the personalities of the surrounding people. Then, for the person at row $x$ and column $y$, after how many days will their personality become $1$? ---- #### Simplified statement There is an $n \times m$ matrix $a$. Define one transformation on a matrix as: change every element in the matrix into the greatest common divisor of itself and its four adjacent elements (up, down, left, right; ignore non-existing ones). Ask for the minimum number of transformations needed for $a_{x,y}$ to become $1$. If $a_{x,y}$ can become $1$ after some number of transformations, output the minimum number; otherwise output $-1$.

The first line contains two integers $n, m$, indicating the number of rows and columns of the matrix. The next $n$ lines each contain $m$ integers. The integer $a_{i,j}$ in row $i$ and column $j$ describes the initial personality of the person at that position. The next line contains two integers $x, y$, indicating the position of a specified person.

Output one integer $d$, meaning that the personality of the person at row $x$ and column $y$ will become $1$ after $d$ days. **In particular**, if it will never become $1$, output $-1$.

#### Sample explanation 3 The personality matrix on the first day (i.e. the initial matrix) is $$ \begin{pmatrix} 3&2&3\\ 2&3&2\\ 3&2&3 \end{pmatrix} $$ The personality matrix on the second day is $$ \begin{pmatrix} 1&1&1\\ 1&1&1\\ 1&1&1 \end{pmatrix} $$ It can be seen that after only one day, $a_{2,2}$ becomes $1$, so the answer is $1$. #### Constraints and conventions **This problem uses bundled tests.** For $100\%$ of the testdata, $1\le n,m\le 2\times 10^3$, $1\le a_{i,j}\le 10^{18}$, $1\le x\le n$, $1\le y\le m$. | Subtask | Score | $n,m$ | Special constraints | | :-----: | :---: | :-----------------: | :----------------------------------------: | | 1 | 1 | / | Guarantee that the personality at the given position will never become $1$ | | 2 | 1 | / | Guarantee that $a_{x,y}=1$ | | 3 | 3 | $ \le 2$ | / | | 4 | 10 | $ \le 10^2$ | / | | 5 | 30 | $ \le 5\times 10^2$ | / | | 6 | 10 | / | Guarantee that for all $a_{i,j} \le 2$ | | 7 | 10 | / | Guarantee that both $x$ and $y$ equal $1$ | | 8 | 35 | / | / | Translated by ChatGPT 5