[HAOI2011]向量 解题报告

题目描述

给你一对数a,b，你可以任意使用(a,b), (a,-b), (-a,b), (-a,-b), (b,a), (b,-a), (-b,a), (-b,-a)这些向量，问你能不能拼出另一个向量(x,y)。

说明：这里的拼就是使得你选出的向量之和为(x,y)

输入输出格式

输入格式：

第一行数组组数t，(t<=50000)

接下来t行每行四个整数a,b,x,y (-2*109<=a,b,x,y<=2*109)

输出格式：

t行每行为Y或者为N，分别表示可以拼出来，不能拼出来

输入输出样例

input

3
2 1 3 3
1 1 0 1
1 0 -2 3

output

Y
N
Y

思路：

这道题是个毒瘤数论。代码很简单但是思路很难(对于蒟蒻的我)

首先，若可以，则有：

$$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$ 有整数解的充要条件是 $\gcd(a,b)\mid c$（裴蜀定理）。

把原式分开则有 $(k+w)a+(q+c)b=x$，$(k-w)b+(q-c)a=y$（记为 [1]式），那么 $(k+w),(q+c),(k-w),(q-c)$ 有整数解的充要条件是 $\gcd(a,b)\mid c$。

但是！！ $k+w$ 有整数解并不代表 $k,w$ 有整数解（比如 $2=0.5+1.5$），其余的情况也是。设 $f=k+w$，$g=k-w$，则 $k=\frac{f+g}{2}$，$w=\frac{f-g}{2}$，那么 $k,w$ 为整数的前提是 $f,g$ 同奇偶（$2\mid(f+g)$ 且 $2\mid(f-g)$），$q,c$ 同理。

分四种情况（讨论的是 [1]式）：

1. 四个数都为偶数：提一个2，则有 $2\cdot\gcd(a,b)\mid x$，同理 $2\cdot\gcd(a,b)\mid y$。
2. 前两个为偶数，后两个为奇数：方程两边加 $b$，得 $(k+w)a+(q+c+1)b=y+b$，则有 $2\cdot\gcd(a,b)\mid y+b$，同理 $2\cdot\gcd(a,b)\mid x+a$。
3. 前两个为奇数，后两个为偶数：同第二种情况，只是把 $a,b$ 换一个位置即可。
4. 四个数都为奇数：都加上 $a+b$，则有 $2\cdot\gcd(a,b)\mid x+a+b$，$2\cdot\gcd(a,b)\mid y+a+b$。

上面四种情况，满足一种即可

code:

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

ll T;
ll x,y,a,b,k;

ll gcd(ll a,ll b)
{
	return (b==0) ? a:gcd(b,a%b);
}

inline bool check(ll x,ll y)
{
	return x%k==0 && y%k==0;
}

int main()
{
	scanf("%lld",&T);
	while(T--)
	{
		scanf("%lld%lld%lld%lld",&a,&b,&x,&y);
		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("Y\n");
		else printf("N\n");
	}
	return 0;
}

代码就是这么简单！！