【BZOJ-2299】向量裴蜀定理 + 最大公约数

2022-11-27 15:36:52

2299: [HAOI2011]向量

Time Limit: 10 Sec Memory Limit: 256 MB
Submit:
1118 Solved: 488
[Submit][Status][Discuss]

Description

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

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

Input

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

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

Output

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

Sample Input

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

Sample Output

Y
N
Y

HINT

样例解释：
第一组：(2,1)+(1,2)=(3,3)
第三组：(-1,0)+(-1,0)+(0,1)+(0,1)+(0,1)=(-2,3)

Source

Solution

首先我们把这些东西组合一下，发现其实这些东西其实相当于是4种变换

(x+-2a,y)/(x,y+-2a)

(x+-2b,y)/(x+-2b,y)

(x+a,y+b)

(x+b,y+a)

那么用裴蜀定理判定一下

证明看这里：折越

Code

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

using namespace std;

int t;

long long d;

long long Gcd(long long a,long long b) {if (b==) return a; return Gcd(b,a%b);}

bool check(long long a,long long b) {if (!(a%d) && !(b%d)) return ; return ;}

long long a,b,x,y;

int main()

{

    scanf("%d",&t);

    while (t--)

        {

            scanf("%lld%lld%lld%lld",&a,&b,&x,&y);

            d=Gcd(a,b)<<;

            if (check(x+a,y+b) || check(x+b,y+a) || check(x+a+b,y+a+b) || check(x,y)) puts("Y");

                else puts("N");

        }

    return ;

}

码农公寓