【HIHOCODER 1599】逃离迷宫4

描述

小Hi被坏女巫抓进一座由无限多个格子组成的矩阵迷宫。

小Hi一开始处于迷宫(x, y)的位置，迷宫的出口在(a, b)。小Hi发现迷宫被女巫施加了魔法，假设当前他处在(x, y)的位置，那么他只能移动到(x+y, y)或者(x, x+y)的位置上。

小Hi想知道自己能不能逃离迷宫。

输入

第一行包含一个整数T，代表测试数据的组数。

以下N行每行包含4个整数x, y, a, b，表示起点在(x, y)，出口在(a, b)。

对于30%的数据，1 ≤ T ≤ 10, 1 ≤ x, y, a, b ≤ 100

对于80%的数据，1 ≤ T ≤ 1000, 1 ≤ x, y, a, b ≤ 1000

对于100%的数据，1 ≤ T ≤ 10000, 1 ≤ x, y, a, b ≤ 109

输出

对于每组数据输出一行YES或者NO，表示小Hi是否能逃离迷宫。

样例输入

2

1 1 8 13

2 2 100 101

样例输出

YES

NO

题解

倒着考虑，就是每次

\[（a，b） \rightarrow （a-b，b）
\]

或者

\[（a，b） \rightarrow （a，b-a）
\]

每次都是大的减小的，而且每次都得减到小于等于小的那个数。

如果（a，b）都没有与（x，y）相等，直接取模就好，因为大的一直要减小的，而且这其中不会出现（x，y）。

如果（a，b）其中一个与（x，y）相等，那么另一个与之差值只有在能够整除它的情况下，才会得到（x，y）。

#include <bits/stdc++.h>

#define ll long long

#define inf 1000000000

#define PI acos(-1)

#define bug puts("here")

#define REP(i,x,n) for(int i=x;i<=n;i++)

#define DEP(i,n,x) for(int i=n;i>=x;i--)

#define mem(a,x) memset(a,x,sizeof(a))

using namespace std;

inline int read(){

    int x=0,f=1;

    char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

    return x*f;

}

int x,y;

bool check(int a,int b){

    if(a<x||b<y) return false;

    if(a==x&&b==y) return true;

    if(a>b){

        if(b==y&&(a-x)%b==0) return true;

        return check(a%b,b);

    }else{

        if(a==x&&(b-y)%a==0) return true;

        return check(a,b%a);

    }

    return false;

}

int main(){

    int T=read();

    while(T--){

        x=read(),y=read();

        int a=read(),b=read();

        printf(check(a,b)?"YES\n":"NO\n");

    }

	return 0;

}

巴特西

【HIHOCODER 1599】逃离迷宫4

描述

输入

输出

样例输入

样例输出

题解

最新文章

热门文章