自动搬运

查看原文

来自洛谷，原作者为

	浅色调 **

搬运于2025-08-24 21:38:36，当前版本为作者最后更新于2018-02-07 18:01:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路：

（我不会调格式啊，可以去看我博客：five20） 首先，我们注意到题目中的向量实际只有4种操作：(a,b),(b,a),(a,-b),(b,-a)。于是由题意得方程组：

$k(a,b)+q(b,a)+w(a,-b)+c(b,-a)=(x,y)$

--> $(k+w)a+(q+c)b=x, (k-w)b+(q-c)a=y$.

由裴蜀定理可得：$ax+by=c$,x和y有整数解的充要条件是 $gcd(a,b)|c$，

证明：令$a=pgcd(a,b),\ b=qgcd(a,b)$,则原式=$(px+qy)gcd(a,b)=c$，显然因为$gcd(a,b)$为整数，而要使x和y为整数，则$gcd(a,b)|c$。

我们回到开始的方程组$(k+w)a+(q+c)b=x,(k-w)b+(q-c)a=y$。由裴蜀定理易得:

使$(k+w),(q+c),(k-w),(q-c)$均为整数的充要条件是：

$gcd(a,b)|x$且$gcd(a,b)|y$。但是注意到(k+w),(k-w)有整数解不一定k和w有整数解（(q+c)和(q-c)是同理的）。此时不妨设$(k+w)=f,(k-w)=g$,则$k=(f+g)/2,w=(f-g)/2$，因为$2|(f+g)$且$2|(f-g)$，显然要使k和w均为整数则f和g均为偶数或均为奇数（(q+c)和(q-c)同理）。

于是我们考虑这四种情况：

1、当(k+w)、(k-w)、(q+c)、(q-c)均为偶数时，$(k+w)a+(q+c)b=x$ 提公因数2结合$gcd(a,b)|x$ => $2gcd(a,b)|x$ 同理 $gcd(a,b)|y$

2、当(k+w)和(k-w)为偶数，(q+c)和(q-c)为奇数时，$(k+w)a+(q+c)b=x$ 先左右两边同加b，再提公因数2 结合$gcd(a,b)|x$ --> $2gcd(a,b)|x+b$ 同理 $2gcd(a,b)|y+a$

3、当(k+w)和(k-w)为奇数，(q+c)和(q-c)为偶数时，$(k+w)a+(q+c)b=x$ 先左右两边同加a，再提公因数2 结合$gcd(a,b)|x$ -->$2gcd(a,b)|x+a$ 同理 $2gcd(a,b)|y+b$

4、当(k+w)、(k-w)、(q+c)、(q-c)均为奇数时，$(k+w)a+(q+c)b=x$ 先左右两边同加a+b，再提公因数2 结合$gcd(a,b)|x$ --> $2gcd(a,b)|x+a+b$ 同理 $2gcd(a,b)|y+a+b$

只要满足上述的任意一种情况，则说明本题k、w、q、c有整数解，说明可行，否则说明无解。

代码：

#include<bits/stdc++.h>
#define il inline
#define ll long long
#define debug printf("%d %s\n",__LINE__,__FUNCTION__)
using namespace std;
ll t,a,b,x,y,k;
il int gi()
{
    ll a=0;char x=getchar();bool f=0;
    while((x<'0'||x>'9')&&x!='-')x=getchar();
    if(x=='-')x=getchar(),f=1;
    while(x>='0'&&x<='9')a=a*10+x-48,x=getchar();
    return f?-a:a;
}
il ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
il bool check(ll x,ll y){return x%k==0&&y%k==0;}
int main()
{
    t=gi();
    while(t--){
        a=gi(),b=gi(),x=gi(),y=gi();
        k=gcd(a,b)*2;
        if(check(x,y)||check(x+a,y+b)||check(x+b,y+a)||check(x+a+b,y+a+b))printf("YE5\n");
        else printf("N0\n");
    }
    return 0;
}