题解 | 小红走网格

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        for (int k = 0; k < t; k++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            int d = sc.nextInt();
            if (canReach(x, c, d) && canReach(y, a, b)) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }
    }


    // 判断是否能通过加减组合达到目标值
    public static boolean canReach(int target, int subtrahend, int addend) {
        if (target == 0) {
            return true;
        }
        //根据裴蜀定理，方程ax+by=c有整数解当且仅当c是a和b的最大公因数的倍数。
        //若target是addend和subtrahend最大公因数的倍数，则可以到达
        int gcd = getGcd(subtrahend, addend);
        return target % gcd == 0;

    }

    //求a和b的最大公因数
    // 使用欧几里得算法计算最大公因数,时间复杂度为 O(log(min(a,b)))，比暴力循环快得多。
    // 欧几里得算法也叫辗转相除法 ，用于计算两个数的最大公因数，其原理基于下面这个定理：
    // 两个整数的最大公因数等于其中较小的那个数和两数相除余数的最大公因数，用公式表示为
    // gcd(m,n)=gcd(n,m%n),其中m>n,且m%n!=0,下面的算法无需强调a和b的大小关系,
    // 因为无论初始时a和b谁大谁小，算法在第一次迭代时会自动调整顺序：
    //若a>b,第一次迭代后,a变为b,b变为a%b
    //若a<b,第一次迭代时,a%b的结果就是a,此时b赋值给a(此时a变为较大值)
    //a%b赋值给b(此时b变为较小值),相当于自动交换了a和b的顺序
    //若a==b,第一次取模后,b=0,直接结束循环,返回a(即b)
    public static int getGcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
        /*int res=Math.min(a,b);//超时
        while(res!=1){
            if(a%res==0 && b%res==0){
                return res;
            }
            res--;
        }
        return res;*/
    }
}