题解 | 小红走网格

#include <iostream>

using namespace std;

int gcd(int a,int b){
    if(b == 0){
        return a;
    }
    return gcd(b,a % b);
}

int main(){
    int n;
    cin >> n;
    int x,y,a,b,c,d;
    for(int i = 1;i <= n;i++){
        cin >> x >> y >> a >> b >> c >> d;
        int e = gcd(a,b);
        bool aa = y % e == 0;
        int f = gcd(c,d);
        int bb = x % f == 0;
        cout << ((aa && bb) ? "YES" : "NO") << endl;
    }
    return 0;
}

思路：欧几里得算法+贝祖定理

贝祖定理，方程ax + by = d存在整数解x和y的充要条件是d是a和b的最大公约数的倍数。也就是说，当且仅当d能被gcd(a, b)整除时，方程有解