题解 | 小红走网格

对于某个轴而言，从0点经若干次增a减b达到目的地，可以用以下式子表示

xa+yb=target （1）

所以能否达到target的问题就变成是否存在整数x，y满足上式。

根据bezout定理可知下式一定成立

xa+yb=gcd(a,b) （2）

所以如果（1）式成立，可知gcd(a,b)整除target

那是否能找到x>0而y<0呢？（相当于增a减b）

也是可以的。

如果x1*a+y1*b=target而不满足增a减b

令x2 = x1+b, y2 = y1-a

仍然有x2*a+y2*b=target

而x2>x1,y2<y1

所以总能找到一组(x,y)满足x>0而y<0

#include <bits/stdc++.h>
using namespace std;

bool check(int dist,int a,int b) {
    int gd = gcd(a,b);
    if(dist % gd)return false;
    return true;
}
int main() {
    int x, y, a, b, c, d, n;
    scanf("%d",&n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d%d%d%d%d", &x, &y, &a, &b, &c, &d);
        if (check(x, d, c) && check(y, a, b)) {
            printf("YES\n");
        } else {
            printf("NO\n");
        }
    }
}
// 64 位输出请用 printf("%lld")