1-Codeforces Round 1091 (Div. 2) and CodeCraft 26题解

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.
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:

Jump $b$ steps right to $A_{\,i,\;((j+b-1)\bmod m)+1}$ , or

Jump $a$ steps down to $A_{\,((i+a-1)\bmod n)+1,\;j}$ .

A special restriction is that he can start with either move, but must alternate between them.
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.
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.
Input
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.
The only line of each test case contains four integers $n, m, a, b$ ( $1 \leq n, m, a, b\leq 10^{9}$ ).
Output
For each test case, print “YES” if Prakul can cover all the tiles of his room, and “NO” otherwise.
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.

等价于

\forall k,(ka \space mod \space n, kb \space mod \space m)和((k + 1)a \space mod \space n, kb \space mod \space b)

是否能遍历到 $[0, n - 1]\times[0,m-1]$ 的所有点

由于 $((k + 1)a \space mod \space n, kb \space mod \space b)$ 可看作 $(ka \space mod \space n, kb \space mod \space m)$ 的平移，首先讨论 $(ka \space mod \space n, kb \space mod \space m)$ 的情况

$(ka \space mod \space n, kb \space mod \space m)$ #

$(ka \space mod \space n)和(kb \space mod \space m)$ 基本一样，不妨讨论 $ka \space mod \space n$ 的情况

1. $ka \space mod \space n$ #

只需讨论 $\forall k \in [0, n - 1]$ 的情况，由带余除法性质可知，其他范围皆可通过平移归约到此情况，形式化地解释如下

\forall k, \exists q,r\in[0, n-1](\text{即}n\text{的标准完全剩余系})\quad s.t. \quad k=q\cdot n + r

故有

ka \space mod \space n = ra \space mod \space n

记 $k = r$ 则有

\forall k \in [0, n-1],ka \space mod \space n

要使动点能随 $k$ 变化遍历所有点，则 $\forall k \in [0, n-1],ka \space mod \space n$ 要能够表示所有行即 $[0, n-1]$ ，即 $n$ 的完全剩余系

要满足这个条件，则 $ka$ 要两两不同余

$n=1$ 时，能表示0即所有行，满足条件且 $gcd(a, n)=1$
$n>1$ 时

设 $\forall k_1 > k_2 \in[0,n-1]$

对于公式
$k_1a-k_2a\equiv (k_1-k_2)a\pmod{n}$
有 $0<k_1-k_2 < n$
1. $gcd(a, n) = 1$ 时
  
  假设
  $(k_1-k_2)a\equiv 0\pmod{n}$
  由于 $gcd(a, n) = 1$ ，故 $a$ 可逆，故有
  $(k_1-k_2)a\equiv 0\Leftrightarrow k_1-k_2\equiv0\pmod{n}$
  由完全剩余系的性质可知当且仅当两者相等时才同余，故得
  $k_1=k_2$
  与条件 $k1 > k_2$ 矛盾，故有结论
  $\forall k_1 \ne k_2 \in[0,n-1],k_1a\not\equiv k_2a \pmod{n}$
  故 $\forall k \in [0, n-1],ka \space mod \space n$ 两两不同行，又总数有 $n$ 个行，故其是 $n$ 的完全剩余系，能表示所有行
2. $gcd(a, n)\ne1$
  
  记 $d=gcd(a,n) > 1$ ，有
  $0<\frac{n}{d} < n$
  故令 $k_1-k_2=\frac{n}{d}$ ，则此时有
  $(k_1-k_2)a\equiv \frac{na}{gcd(n,a)}\equiv lcm(n,a)\equiv0\pmod{n}$
  故有结论，此时 $[0, n-1]$ 会有 $\frac{n}{d}$ 及其倍数使行重复，又总数只有 $n$ 个行，故能表示的行 $<n$ ，不满足条件

故当且仅当 $gcd(a,n)=1$ 时 $ka \space mod \space n$ 能表示所有行

2. $kb \space mod \space n$ #

同理可得当且仅当 $gcd(b,m)=1$ 时 $kb \space mod \space n$ 能表示所有列

3. $(ka \space mod \space n, kb \space mod \space m)$ #

即使各自能表示所有行，表示所有列，在遍历 $k$ 的过程中动点仍有可能重复

考虑 $(ka \space mod \space n, kb \space mod \space m)$ 重复的情况，只有

\forall k_1 > k_2, \begin{cases} k_1a\equiv k_2a \pmod{n} \\ k_1b\equiv k_2b \pmod{m} \end{cases} \overset{gcd(a,n)=1,gcd(b,m)=1}\Leftrightarrow \forall k_1 - k_2 > 0, \begin{cases} k_1-k_2\equiv 0 \pmod{n} \\ k_1-k_2\equiv 0 \pmod{m} \end{cases}

记 $t=k_1-k_2$ 对于

\begin{cases} t\equiv 0 \pmod{n} \\ t\equiv 0 \pmod{m} \end{cases}

由扩展欧几里得定理解得

t\equiv0 \pmod{lcm(n,m)}\Leftrightarrow k_1\equiv k_2 \pmod{lcm(n,m)}

由于

\forall k,k=q\cdot lcm(n,m)+r,0\le r < lcm(n,m)

故 $k$ 可归约为 $[0,lcm(n,m)-1]$ 即 $lcm(n,m)$ 的完全剩余系，其余点总能在完全剩余系中找到等价的点，而完全剩余系中的点模 $lcm(n,m)$ 不同余，故为不同点，总计有 $lcm(n,m)$ 个不同点，可简单的解释为 $k\rightarrow(ka\space mod \space n, kb\space mod \space m)$ 的映射以 $lcm(n,m)$ 为最小周期，即当 $k$ 在 $[0, lcm(n,m)-1]$ 取值时恰好遍历所有不同点，故共有 $lcm(n,m)$ 个不同点

4. $((k + 1)a \space mod \space n, kb \space mod \space b)$ #

由于 $((k + 1)a \space mod \space n, kb \space mod \space b)$ 可看作 $(ka \space mod \space n, kb \space mod \space m)$ 的平移，故也能遍历总计有 $lcm(n,m)$ 个不同点，那么是否和 $(ka \space mod \space n, kb \space mod \space m)$ 重复呢？若有重复点，则

\begin{cases} (k_1+1)a\equiv k_2a \pmod{n} \\ k_1b\equiv k_2b \pmod{m} \end{cases} \overset{gcd(a,n)=1,gcd(b,m)=1}\Leftrightarrow \begin{cases} k_1+1\equiv k_2 \pmod{n} \\ k_1\equiv k_2 \pmod{m} \end{cases} \overset{t=k_2-k_1}\Leftrightarrow \begin{cases} t\equiv 1 \pmod{n} \\ t\equiv 0 \pmod{m} \end{cases}

有解，由裴蜀定理得，要使其有解则

1 \equiv 0 \pmod{gcd(n,m)} \Leftrightarrow gcd(n,m)=1

其余情况则无解，与 $(ka \space mod \space n, kb \space mod \space m)$ 无重复

5. Conclusion#

$gcd(n,m)=1$ 时

$(ka \space mod \space n, kb \space mod \space m)$ 能表示 $lcm(n,m)\overset{gcd(n,m)=1}=nm$ 个点，故能表示 $[0, n - 1]\times[0,m-1]$ 所有点，满足条件
$gcd(n,m)\ne1$ 时

$((k + 1)a \space mod \space n, kb \space mod \space b)$ 和 $(ka \space mod \space n, kb \space mod \space m)$ 可表示总共 $2\times lcm(n,m)$ 个互不相同的点

要使其能遍历 $[0, n - 1]\times[0,m-1]$ 所有点则

$2\times lcm(n,m) \ge nm \Leftrightarrow \frac{nm}{lcm(n,m)} = gcd(n,m) \le 2$

音乐

音乐

$(ka \space mod \space n, kb \space mod \space m)$ #

1. $ka \space mod \space n$ #

2. $kb \space mod \space n$ #

3. $(ka \space mod \space n, kb \space mod \space m)$ #

4. $((k + 1)a \space mod \space n, kb \space mod \space b)$ #

5. Conclusion#

文章分享

评论区

音乐

目录

音乐

音乐

1-Codeforces Round 1091 (Div. 2) and CodeCraft 26题解

(ka mod n,kb mod m)(ka \space mod \space n, kb \space mod \space m)(ka mod n,kb mod m)#

1. ka mod nka \space mod \space nka mod n#

2. kb mod nkb \space mod \space nkb mod n#

3. (ka mod n,kb mod m)(ka \space mod \space n, kb \space mod \space m)(ka mod n,kb mod m)#

4. ((k+1)a mod n,kb mod b)((k + 1)a \space mod \space n, kb \space mod \space b)((k+1)a mod n,kb mod b)#

5. Conclusion#

文章分享

评论区

音乐

目录

$(ka \space mod \space n, kb \space mod \space m)$ #

1. $ka \space mod \space n$ #

2. $kb \space mod \space n$ #

3. $(ka \space mod \space n, kb \space mod \space m)$ #

4. $((k + 1)a \space mod \space n, kb \space mod \space b)$ #