题解 P2520 【[HAOI2011]向量】

· · 题解

思路：

（我不会调格式啊，可以去看我博客：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)均为整数的充要条件是：

　　于是我们考虑这四种情况： 　　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;
}