「NOIP 模拟赛」Azuki loves chess - 数论

发表于 | 分类于

在一个无穷大的中国象棋棋盘上，马每次可以在一个方向上移动一个单位，在另一个方向上移动两个单位。现将规则改为，马每次可以在一个方向上移动 aa 个单位，在另一个方向上移动 bb 个单位。问放置在 (0,0)(0,0) 的马能否移动到 (n,m)(n,m)。

链接

LYOI #406

题解

题意可转化为，判断以下关于 x,y,z,wx,y,z,w 的方程是否存在整数解：

x(a,b)+y(b,a)+z(−b,a)+w(−a,b)=(n,m)x(a,b)+y(b,a)+z(-b,a)+w(-a,b)=(n,m)

将两维分开考虑，即

ax+by−bz−aw=nbx+ay+az+bw=m \begin{aligned} ax+by-bz-aw&=n \\ bx+ay+az+bw&=m \end{aligned}

两式相加得

(a+b)x+(a+b)y+(a−b)z−(a−b)w=n+m (a+b)x+(a+b)y+(a-b)z-(a-b)w=n+m

整理这三个式子得到

a(x−w)+b(y−z)=nb(x+w)+a(y+z)=m(a+b)(x+y)+(a−b)(z−w)=n+m \begin{aligned} a(x-w)+b(y-z)&=n \\ b(x+w)+a(y+z)&=m \\ (a+b)(x+y)+(a-b)(z-w)&=n+m \end{aligned}

结论：这三个二元一次不定方程同时有解，是本题答案为 Yes 的充要条件，即：

{gcd(a,b)∣ngcd(a,b)∣mgcd(a+b,a−b)∣n+m \begin{cases} \gcd(a,b)|n \\ \gcd(a,b)|m \\ \gcd(a+b,a-b)|n+m \end{cases}

必要性显然，下证充分性。

如果前两个方程有解，那么，通过它们的解构造出一组原方程一组可行解的方法是：

{x=(x+w)+(x−w)2y=(y+z)+(y−z)2z=(y+z)−(y−z)2w=(x+w)−(x−w)2 \begin{cases} x=\frac{(x+w)+(x-w)}{2} \\ y=\frac{(y+z)+(y-z)}{2} \\ z=\frac{(y+z)-(y-z)}{2} \\ w=\frac{(x+w)-(x-w)}{2} \end{cases}

所以，原题有解，等价于前两个方程有解，且对应位置的未知数值的奇偶性相同。即，对于以下两个方程，存在一组整数解，使得 p1p_1 与 p2p_2 奇偶性相同，q1q_1 与 q2q_2 奇偶性相同。

ap1+bq1=nbp2+aq2=m \begin{aligned} ap_1+bq_1&=n \\ bp_2+aq_2&=m \end{aligned}

我们可以将上式都除去 gcd(a,b)\gcd(a,b)，即

a′=agcd(a,b)b′=bgcd(a,b)n′=ngcd(a,b)m′=mgcd(a,b) \begin{aligned} a'&=\frac{a}{\gcd(a,b)} \\ b'&=\frac{b}{\gcd(a,b)} \\ n'&=\frac{n}{\gcd(a,b)} \\ m'&=\frac{m}{\gcd(a,b)} \end{aligned}

上述方程化为

a′p1+b′q1=n′b′p2+a′q2=m′ \begin{aligned} a'p_1+b'q_1&=n' \\ b'p_2+a'q_2&=m' \end{aligned}

下面证明，在第三个方程有解的前提条件下，从前两个方程的任意一组解，都可得到一组满足条件（对应未知数的值奇偶性相同）的解。

由于 a′,b′a',b' 互质，所以它们不可能都是偶数。

当 a′,b′a',b' 一奇一偶时

根据一元二次不定方程 a′x+b′y=ca'x+b'y=c 的通解公式（tt 为任意整数）：

xi=x0+t⋅b′yi=y0−t⋅a′ \begin{aligned} x_i=x_0+t\cdot b'\\ y_i=y_0-t\cdot a' \end{aligned}

调整 tt 的大小，可以在保持 a′,b′a',b' 中一个数的奇偶性不变的情况下，调整另一个数的奇偶性。

所以可以通过调整，使得

a′p1+b′q1=n′b′p2+a′q2=m′ \begin{aligned} a'p_1+b'q_1&=n' \\ b'p_2+a'q_2&=m' \end{aligned}

中 p1p_1 的奇偶性与 p2p_2 相同，q2q_2 的奇偶性与 q1q_1 相同。

当 a′,b′a',b' 均为奇数时

方程三 (a′+b′)(x+y)+(a′−b′)(z−w)=n′+m′(a'+b')(x+y)+(a'-b')(z-w)=n'+m' 有解的充要条件为 gcd(a′+b′,a′−b′)∣n′+m′\gcd(a'+b',a'-b')|n'+m'。而 gcd(a′+b′,a′−b′)=gcd(a′+b′,a′+b′−(a′−b′))=gcd(a′+b′,2b′)\gcd(a'+b',a'-b')=\gcd(a'+b',a'+b'-(a'-b'))=\gcd(a'+b',2b') 一定是一个偶数（并且其值为 22，因为 a′,b′a',b' 互质），所以此时 n′+m′n'+m' 一定是偶数，所以 n′,m′n',m' 一定均为奇数或均为偶数。

如果 n′,m′n',m' 均为奇数，以方程一 a′p1+b′q1=n′a'p_1+b'q_1=n' 为例，只有当 a′p1a'p_1 和 b′q1b'q_1 一奇一偶时，方程才有解，这时 p1,q1p_1,q_1 一定是一奇一偶。方程二同理。

如果 n′,m′n',m' 均为偶数，以方程一 a′p1+b′q1=n′a'p_1+b'q_1=n' 为例，只有当 a′p1a'p_1 和 b′q1b'q_1 均为奇数时，方程才有解，这时 p1,q1p_1,q_1 一定均为奇数。方程二同理。

Q.E.D.

代码

#include <cstdio>
#include <algorithm>

int main() {
    freopen("chess.in", "r", stdin);
    freopen("chess.out", "w", stdout);
    int T;
    scanf("%d", &T);
    while (T--) {
        long long a, b, n, m;
        scanf("%lld %lld %lld %lld", &a, &b, &n, &m);
        puts((n % std::__gcd(a, b) == 0 && m % std::__gcd(a, b) == 0 && (n + m) % std::__gcd(a + b, a - b) == 0) ? "Yes" : "No");
    }
}