在一个无穷大的中国象棋棋盘上,马每次可以在一个方向上移动一个单位,在另一个方向上移动两个单位。现将规则改为,马每次可以在一个方向上移动 个单位,在另一个方向上移动 个单位。问放置在 的马能否移动到 。
链接
题解
题意可转化为,判断以下关于 的方程是否存在整数解:
将两维分开考虑,即
两式相加得
整理这三个式子得到
结论:这三个二元一次不定方程同时有解,是本题答案为 Yes 的充要条件,即:
必要性显然,下证充分性。
如果前两个方程有解,那么,通过它们的解构造出一组原方程一组可行解的方法是:
所以,原题有解,等价于前两个方程有解,且对应位置的未知数值的奇偶性相同。即,对于以下两个方程,存在一组整数解,使得 与 奇偶性相同, 与 奇偶性相同。
我们可以将上式都除去 ,即
上述方程化为
下面证明,在第三个方程有解的前提条件下,从前两个方程的任意一组解,都可得到一组满足条件(对应未知数的值奇偶性相同)的解。
由于 互质,所以它们不可能都是偶数。
当 一奇一偶时
根据一元二次不定方程 的通解公式( 为任意整数):
调整 的大小,可以在保持 中一个数的奇偶性不变的情况下,调整另一个数的奇偶性。
所以可以通过调整,使得
中 的奇偶性与 相同, 的奇偶性与 相同。
当 均为奇数时
方程三 有解的充要条件为 。而 一定是一个偶数(并且其值为 ,因为 互质),所以此时 一定是偶数,所以 一定均为奇数或均为偶数。
如果 均为奇数,以方程一 为例,只有当 和 一奇一偶时,方程才有解,这时 一定是一奇一偶。方程二同理。
如果 均为偶数,以方程一 为例,只有当 和 均为奇数时,方程才有解,这时 一定均为奇数。方程二同理。
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");
}
}