Editorial : Grid Covering
This section matches the decision rule in model_sol.cpp.
For each test case, compute $g_{na} = \gcd(n, a)$, $g_{mb} = \gcd(m, b)$, and $g_{nm} = \gcd(n, m)$. The program prints NO if $g_{na} > 1$ or $g_{mb} > 1$ or $g_{nm} > 2$, and prints YES otherwise. This uses $O(\log \max(n, m, a, b))$ time per test case.
Work in $0$-based coordinates on $\mathbb{Z}_n \times \mathbb{Z}_m$.
Because moves must alternate, look at 2 consecutive moves.
If we start with down:
- move 1: $(x,y)\to(x+a,y)$,
- move 2: $(x+a,y)\to(x+a,y+b)$.
So every 2 moves apply translation by vector $(a,b)$.
Define:
$$ S_0=\{(ta \bmod n,\; tb \bmod m)\mid t\ge 0\}, $$positions at even times, and
$$ S_1=\{((t+1)a \bmod n,\; tb \bmod m)\mid t\ge 0\}, $$positions at odd times.
Visited cells are exactly $S_0 \cup S_1$.
- To hit every row, multiples of $a$ mod $n$ must cover all residues: $\gcd(n,a)=1$.
- To hit every column, multiples of $b$ mod $m$ must cover all residues: $\gcd(m,b)=1$.
Now with these two, order of $(a,b)$ is:
$$ L=\operatorname{lcm}(n,m)=\frac{nm}{\gcd(n,m)}. $$So $|S_0|=|S_1|=L$, hence
$$ |S_0\cup S_1|\le 2L. $$To cover all $nm$ cells, we need:
$$ nm\le 2L \iff \gcd(n,m)\le 2. $$So all three are necessary:
$$ \gcd(n,a)=1,\quad \gcd(m,b)=1,\quad \gcd(n,m)\le 2. $$- If $\gcd(n,m)=1$, then $L=nm$, so $S_0$ already has all cells.
- If $\gcd(n,m)=2$, then $L=nm/2$. Also $S_0$ and $S_1$ are disjoint, so union size is $nm$.
Therefore these conditions are also sufficient.
So answer is YES iff:
(Starting with right is symmetric and gives the same criterion.)
Per test case, only three gcd computations:
- Time: $O(\log \max(n,m,a,b))$.
- Extra space: $O(1)$.