2020牛客NOIP赛前集训营-提高组（第一场） A题 题解

本场全部题解见此

更好的阅读体验

A 牛牛的方程式

题意简述

给定 ，询问是否存在一组整数解 ，满足 。

多测， 。

算法标签

数论 同余

算法分析

如果只有两项，即 这种形式，可以直接套用裴蜀定理，该方程有整数解等价于 。

由上面的式子，我们不难发现， 可以表示所有整除 的数。

那么原方程有整数解等价于 有整数解。

同理，这个方程有整数解等价于 。

注意特判 ，即 的情况。

代码实现

#include<bits/stdc++.h>
using namespace std;
#define maxn 1000005
#define maxm 2000005
#define inf 0x3f3f3f3f
#define int long long
#define mod 1000000007
#define local
void file(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
template <typename Tp>void read(Tp &x){
    x=0;int fh=1;char c=getchar();
    while(c>'9'||c<'0'){if(c=='-'){fh=-1;}c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}x*=fh;
}
int a,b,c,d;
int gcd(int x,int y){return y?gcd(y,x%y):x;}
signed main(){
    int T;
    read(T);
    while(T--){
        read(a);read(b);read(c);read(d);
        int ans=gcd(gcd(a,b),c);
        if(ans==0)puts(d?"NO":"YES");
        else puts(d%ans==0?"YES":"NO");
    }
    return 0;
}