题解 | 小红走网格

import java.util.Scanner;

/**
 * @author supermejane
 * @date 2025/10/6
 * @description BGN50 小红走网格
 */
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        while (n-- > 0) {
            int x = in.nextInt();
            int y = in.nextInt();
            int y_add = in.nextInt();
            int y_del = in.nextInt();
            int x_del = in.nextInt();
            int x_add = in.nextInt();
            System.out.println(illegal(y_add, y_del, y) && illegal(x_add, x_del, x) ? "YES" : "NO");
        }
    }

    //c是不是a, b的线性组合
    public static boolean illegal(int a, int b, int c) {
        return c % gcd(Math.max(a, b), Math.min(a, b), new int[2]) == 0;
    }

    //辗转相除
    public static int gcd(int a, int b, int[] xy) {

        if (b == 0) {
            xy[0] = 1;
            xy[1] = 0;
            return a;
        } else {
            int g = gcd(b, a % b, xy);
            //非必要，如果要求线性组合系数可以使用
            //回溯,这个xy表示a * xy[0] + b * xy[1] = 最小公约数，即a * xy[0] + b * xy[1] = b * xy[0]' + (a % b) * xy[1]'
            //由于左边a * xy[0] + b * xy[1] = (a / b * xy[0] + xy[1]) * b + a % b * xy[0], 就是说(a / b * xy[0] + xy[1]) = xy[0]'并且xy[0] = xy[1]'
            //我上面是正推，回溯是反推，所以xy'和xy反一下就行了
            int x = xy[0];
            int y = xy[1];
            xy[0] = y;
            xy[1] = x - a / b * y;

            return g;
        }
    }

    //最小公倍数
    public static int lcm(int a, int b) {
        int g = gcd(a, b, new int[2]);

        return a * b / g;
    }
}

//没学过数论，搜Gpt现学的,包括贝祖定理，gcd, lcm
/*
要判断一个数字 c 是否能表示为 c = m*a + n*b（其中 m 和 n 是整数，可正可负），核心依据是数论中的贝祖定理（Bezout's Identity）。
结论
一个数 c 能表示为 m*a + n*b 的充要条件是：c 是 a 和 b 的最大公约数（gcd(a, b)）的整数倍。
即：c % gcd(a, b) == 0
*/