水题，但是没做对
题目描述
牛牛最近对三元一次方程非常感兴趣。众所周知，三元一次方程至少需要三个方
程组成一个方程组，才有可能得出一组解。
牛牛现在想要知道对于方程ax + by + cz = d中有没有至少存在一组{x, y, z}的解，
且x, y, z都为整数，使得方程式成立。输入格式
第一行输入一个正整数 T，表示测试点中测试样例的组数。
接下来T行，每行四个整数a, b, c, d表示方程ax + by + cz = d中的a, b, c, d输出格式
如果至少存在一组x, y, z能够满足方程式等式成立，且x, y, z均为整数，请输出
“YES”，否则请输出”NO”。样例输入1
2 3 1 2 0 2 8 8 3样例输出1
YES NO样例1解释
13+(-1)1+(-1)*2=0
得到一组 x,y,z 的解为{1,-1,-1}为整数使得等式成立，所以输出”YES”。
不存在 x,y,z 为整数使得方程 2x+8y+8z=3 成立，所以输出”NO”。数据范围
对于10%的测试数据，保证T = 1,−10 ≤ 𝑎, b, c ≤ 10
对于30%的测试数据，保证−100 ≤ 𝑎, b, c ≤ 100
对于100%的测试数据，保证−10^18 ≤ a, b, c ≤ 10^18
,1 ≤ 𝑇 ≤ 100
思路
看到方程，自然会想到exgcd求二元一次不定方程，或者是裴蜀定理：
ax+by=gxd(a,b)*k=m
GCD
先来看看gcd，这里我用辗转相除法来做的，我以前在网上看到过很多证明，但是都没看懂，这里给出我自己的解释（不知道有没有人和我一样），希望这能够帮到你（讲的真的很详细，认真看完哦）
gcd是用来求最大公约数的。举个例子，我们先求54和24的最大公约数，假设我们已经知道了这两个数的最大公约数是6，那么我们可以把54变为6*9（系数乘上最小公约数），24也能够变为6*4（也是系数乘上最小公约数），我们将较大的数减去较小的数（54-24），直到不能减为止（54-24变为30-24再变为6-24）。因为开始的时候54和24都是最小公约数的倍数，所以这时候剩下的6也一定是最小公约数的倍数。我们继续减，当然，我们将24和6位置互换一下，继续用24减去6，我们发现，减去4次6以后，24变为了0。这时候我们就得到了最小公倍数6。
我们来看一下这个思路能不能化简一下，我们一直减这个操作可以化简为取余的操作。
再放一个程序int gcd(int a,int b){ if(a==1||b==0){ return a; } if(a<b){ swap(a,b); } return gcd(b,a%b); }如果这两个数互质，那么他们会一直取余，直到其中一个数变为1，这时候返回1就可以了
最后再用代数来表示一下
将数x和y表示为a*d和b*d（d是最小公约数），x%y=（a-b）* d，直到a-b等于1
裴蜀定理
再让我们来看看裴蜀定理是什么：
对于给定的两个数a和b，一定有两个数（x，y）满足ax+by=gcd(a,b)
证明：
我们还是将a和b表示为p*d和q*d，那么原式就为p*x*d+q*y*d=gcd(a,b)*k
就可以看为（p*x+q*y）=k，且一定有k可以成立
我们这就证明了裴蜀定理
回到题目
三个数？我们就将它简化，将裴蜀定理带入得
gcd（a,b）*k1+c*z=d
gcd（a,b,c）*k2=d
那么我们只要判断d能否整除这三个数的最大公约数
if(a!=0&&b!=0&&c!=0&&d!=0){
if(d%gcd(gcd(a,b),c)==0){
cout<<"YES"<<endl;
continue;
}
}
这就是核心代码，剩下的，就是一堆特判，因为再gcd中，不能判断0和其他数的最小公约数
代码
#include<bits/stdc++.h>
using namespace std;
long long T,a,b,c,d;
long long gcd(long long a,long long b){
if(a==1||b==0){
return a;
}
if(a<b){
swap(a,b);
}
return gcd(b,a%b);
}
int main(){
freopen("niuniufx.in","r",stdin);
freopen("niuniufx.out","w",stdout);
scanf("%lld",&T);
for(int i=1;i<=T;i++){
scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
a=abs(a);
b=abs(b);
c=abs(c);
d=abs(d);
if(a!=0&&b!=0&&c!=0&&d!=0){
if(d%gcd(gcd(a,b),c)==0){
cout<<"YES"<<endl;
continue;
}
}
if(d==0){
cout<<"YES"<<endl;
continue;
}
if(a==0&&b==0&&c==0){
cout<<"NO"<<endl;
continue;
}
if(a==0&&b==0&&d%c==0){
cout<<"YES"<<endl;
continue;
}
if(a==0&&c==0&&d%b==0){
cout<<"YES"<<endl;
continue;
}
if(c==0&&b==0&&d%a==0){
cout<<"YES"<<endl;
continue;
}
if(a==0&&d%gcd(b,c)==0){
cout<<"YES"<<endl;
continue;
}
if(b==0&&d%gcd(a,c)==0){
cout<<"YES"<<endl;
continue;
}
if(c==0&&d%gcd(b,a)==0){
cout<<"YES"<<endl;
continue;
}
cout<<"NO"<<endl;
}
return 0;
}
原文地址：http://www.cnblogs.com/GXYZY/p/16869422.html
