「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+bybzaw=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+(ab)z(ab)w=n+m (a+b)x+(a+b)y+(a-b)z-(a-b)w=n+m

整理这三个式子得到

a(xw)+b(yz)=nb(x+w)+a(y+z)=m(a+b)(x+y)+(ab)(zw)=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,ab)n+m \begin{cases} \gcd(a,b)|n \\ \gcd(a,b)|m \\ \gcd(a+b,a-b)|n+m \end{cases}

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

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

{x=(x+w)+(xw)2y=(y+z)+(yz)2z=(y+z)(yz)2w=(x+w)(xw)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_1p2p_2 奇偶性相同,q1q_1q2q_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}

上述方程化为

ap1+bq1=nbp2+aq2=m \begin{aligned} a'p_1+b'q_1&=n' \\ b'p_2+a'q_2&=m' \end{aligned}

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

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

a,ba',b' 一奇一偶时

根据一元二次不定方程 ax+by=ca'x+b'y=c 的通解公式(tt 为任意整数):

xi=x0+tbyi=y0ta \begin{aligned} x_i=x_0+t\cdot b'\\ y_i=y_0-t\cdot a' \end{aligned}

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

所以可以通过调整,使得

ap1+bq1=nbp2+aq2=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,ba',b' 均为奇数时

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

如果 n,mn',m' 均为奇数,以方程一 ap1+bq1=na'p_1+b'q_1=n' 为例,只有当 ap1a'p_1bq1b'q_1 一奇一偶时,方程才有解,这时 p1,q1p_1,q_1 一定是一奇一偶。方程二同理。

如果 n,mn',m' 均为偶数,以方程一 ap1+bq1=na'p_1+b'q_1=n' 为例,只有当 ap1a'p_1bq1b'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");
    }
}