小红走网格

思路

小红从原点 (0,0) 出发，每次可以向上走 a 步、向下走 b 步、向左走 c 步、向右走 d 步，问能否到达 (x, y)。

把 x 和 y 两个方向拆开独立考虑：

  • x 方向：向右走 r 次、向左走 s 次，最终 x 坐标 = rd - sc，其中 r, s >= 0。
  • y 方向：向上走 p 次、向下走 q 次，最终 y 坐标 = pa - qb，其中 p, q >= 0。

关键数学结论：对于非负整数 r, s，rd - sc 能表示的整数集合恰好是 gcd(c, d) 的所有倍数。

为什么？由裴蜀定理，存在整数 r', s' 使得 r'd + s'c = gcd(c, d)，因此 gcd(c, d) 的任意倍数都能用 d 和 c 的整数线性组合表示。虽然裴蜀定理的解可能有负数，但只要给 r' 和 s' 分别加上足够大的 c 和 d 的倍数，就能把它们都调成非负的（总值不变，因为加的是 cd - dc = 0）。

所以判定条件很简单：

  • x % gcd(c, d) == 0 且 y % gcd(a, b) == 0 就输出 YES，否则 NO。

代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        long long x, y, a, b, c, d;
        scanf("%lld%lld%lld%lld%lld%lld", &x, &y, &a, &b, &c, &d);
        long long gx = __gcd(c, d);
        long long gy = __gcd(a, b);
        puts(x % gx == 0 && y % gy == 0 ? "YES" : "NO");
    }
    return 0;
}

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine().trim());
        StringBuilder sb = new StringBuilder();
        while (T-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            long x = Long.parseLong(st.nextToken());
            long y = Long.parseLong(st.nextToken());
            long a = Long.parseLong(st.nextToken());
            long b = Long.parseLong(st.nextToken());
            long c = Long.parseLong(st.nextToken());
            long d = Long.parseLong(st.nextToken());
            long gx = gcd(c, d);
            long gy = gcd(a, b);
            sb.append(x % gx == 0 && y % gy == 0 ? "YES" : "NO").append('\n');
        }
        System.out.print(sb);
    }
    static long gcd(long a, long b) {
        a = Math.abs(a); b = Math.abs(b);
        while (b != 0) { long t = b; b = a % b; a = t; }
        return a;
    }
}

import sys
import math
input = sys.stdin.readline

def main():
    t = int(input())
    out = []
    for _ in range(t):
        x, y, a, b, c, d = map(int, input().split())
        gx = math.gcd(c, d)
        gy = math.gcd(a, b)
        out.append("YES" if x % gx == 0 and y % gy == 0 else "NO")
    print('\n'.join(out))

main()

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line));
rl.on('close', () => {
    function gcd(a, b) {
        if (a < 0n) a = -a;
        if (b < 0n) b = -b;
        while (b !== 0n) { let t = b; b = a % b; a = t; }
        return a;
    }
    let idx = 0;
    const T = parseInt(lines[idx++]);
    const out = [];
    for (let i = 0; i < T; i++) {
        const parts = lines[idx++].trim().split(/\s+/);
        const x = BigInt(parts[0]);
        const y = BigInt(parts[1]);
        const a = BigInt(parts[2]);
        const b = BigInt(parts[3]);
        const c = BigInt(parts[4]);
        const d = BigInt(parts[5]);
        const gx = gcd(c, d);
        const gy = gcd(a, b);
        out.push(x % gx === 0n && y % gy === 0n ? "YES" : "NO");
    }
    console.log(out.join('\n'));
});

复杂度分析

  • 时间复杂度: ，每组数据做两次 GCD 计算。
  • 空间复杂度: ，只用常数变量。

小结

这道题的核心是把二维问题拆成两个独立的一维问题，然后用裴蜀定理判断可达性。rd - sc（r, s 非负）能表示的值恰好是 gcd(c, d) 的所有整数倍，因此只需判断 x 和 y 分别能否被对应方向步长的 GCD 整除即可。