2217C.md (3155B)
1 Source: https://codeforces.com/problemset/problem/2217/C 2 3 C. Grid Covering 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Prakul has been working hard setting problems for Codecraft. When he's deep in thought, he likes jumping around his room in weird but specific ways. After some time, he wonders if jumping in this manner can cover all the tiles of his room. 22 23 Prakul's room can be considered as a grid $A$ consisting of $n$ rows and $m$ columns. He starts walking from $A_{1,1}$. If he is currently at $A_{i,j}$ he can do either of the following moves: 24 25 * Jump $b$ steps right to $A_{\,i,\;((j+b-1)\bmod m)+1}$, or 26 * Jump $a$ steps down to $A_{\,((i+a-1)\bmod n)+1,\;j}$. 27 28 A special restriction is that he can start with either move, but must alternate between them. 29 30 Note that his room is quite special as it wraps around itself. Moving one step right from the $m$-th column places him in the $1$-st column. Similarly, moving one step down from the $n$-th row places him in the $1$-st row. 31 32 Since he still has to work on problemsetting, he needs your help. Determine if he can visit all tiles in $A$ in a finite number of jumps. 33 34 Input 35 36 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows. 37 38 The only line of each test case contains four integers $n, m, a, b$ ($1 \leq n, m, a, b\leq 10^{9}$). 39 40 Output 41 42 For each test case, print "YES" if Prakul can cover all the tiles of his room, and "NO" otherwise. 43 44 You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses. 45 46 Example 47 48 Input 49 50 ``` 51 10 52 53 1 1 1 1 54 55 2 2 1 1 56 57 4 2 2 1 58 59 6 9 6 7 60 61 67 42 42 67 62 63 3411 4134 32 23 64 65 90234 143124 232 323 66 67 69387963 98793214 9791 4324786 68 69 985865 578977 899368 447605 70 71 1000000000 1000000000 1000000000 1000000000 72 ``` 73 74 Output 75 76 ``` 77 YES 78 79 YES 80 81 NO 82 83 NO 84 85 YES 86 87 NO 88 89 NO 90 91 NO 92 93 YES 94 95 NO 96 ``` 97 98 Note 99 100 In the second test case: $n=2$, $m=2$, $a=1$, $b=1$. One possible way to cover the grid is if Prakul starts by moving down: 101 102 * Start at $(1, 1)$. 103 * Jump down $a=1$ tile: $(1, 1) \to (2, 1)$. 104 * Jump right $b=1$ tile: $(2, 1) \to (2, 2)$. 105 * Jump down $a=1$ tile: $(2, 2) \to (1, 2)$. 106 * Jump right $b=1$ tile: $(1, 2) \to (1, 1)$. 107 108 The sequence of visited tiles is $\{(1, 1), (2, 1), (2, 2), (1, 2)\}$. In this case, all $2 \cdot 2 = 4$ tiles are covered, so the answer would be "YES". Notice that Prakul wraps around the grid in the last two moves. 109 110 In the third test case: $n=4$, $m=2$, $a=2$, $b=1$. If Prakul starts by moving down, the moves look like: 111 112 * Start at $(1, 1)$. 113 * Jump down $a=2$ tiles: $(1, 1) \to (3, 1)$. 114 * Jump right $b=1$ tile: $(3, 1) \to (3, 2)$. 115 * Jump down $a=2$ tiles: $(3, 2) \to (1, 2)$. 116 * Jump right $b=1$ tile: $(1, 2) \to (1, 1)$. 117 * $\cdots$ 118 119 In this case, the tiles $\{(2, 1), (2, 2), (4, 1), (4, 2)\}$ remain unvisited forever. Since not all tiles can be covered, the answer is "NO". It can be shown that even if Prakul started by moving right in the first move, the answer would not have changed.