本文共 1465 字，大约阅读时间需要 4 分钟。

[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*10^{9<=a,b,x,y<=2*10}9)

输出格式：

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)|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)|c. 但是！！* k+w有整数解并不代表k,w有整数解(比如2=0.5+1.5),其余的情况也是。 想一下，设f=k+w,g=k-w,则k=(f+g)/2,w=(f-g)/2,那么k,w为整数的前提是，f,g都为偶数或奇数（2|(f-g)&&2|(f+g)）, q,c同理。

分四种情况(讨论的是[1]式)

1. 假如四个数都为偶数,(k+w)a+(q+w)b=c,因为都是偶数所以提一个2,则有 2gcd(a,b)|x.,同理2gcd(a,b)|y
2. 若前两个数为偶数,后面为奇数那么可以在方程两边都加上b.得到:(k+w)a+(q+c)b+b=c+b. 进一步得(k+w)a+(q+c+1)b=y+b;按照第一个种情况思路，则有:2 * gcd(a,b)|y+b ，同理 2*gcd(a,b)|x+a
3. 当前面为寄，后面为偶时，同第二种情况，只是把a,b换一个位置即可
4. 都为奇数时，那么都加上a+b，然后则有2 * gcd(a,b)|x+a+b 2*gcd(a,b)|y+a+b

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

code:

#include
   
    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;}
   

代码就是这么简单！！

转载地址：http://dyuci.baihongyu.com/