Gcd 2023牛客暑期多校训练营6 G

登录—专业IT笔试面试备考平台_牛客网

题目大意：给出一个集合，集合中初始有2个数x,y(x!=y)，每次操作可以将集合中任意两个不等的数的差放入集合或者将两个不等的数的gcd放入集合，给出一个数z，问z有没有可能出现在集合里

1<=t<=1e5;0<x,y,z<=1e9

思路：不妨令x>y,因为我们可以得到x,y的最大公因数，然后我们可以用x不断减去最大公因数就能得到小于x的所有是gcd的倍数的数，但因为两个相间的数不能相等，所以如果初始两个数中没有0就得不到0，然后用1倍gcd减二倍gcd就能得到负一倍的gcd，再用y-负数就能得到所有大于y的gcd的倍数，所以只要z不等于0且z是gcd的倍数，就能输出YES

//#include<__msvc_all_public_headers.hpp>
#include<bits/stdc++.h>
using namespace std;
int gcd(int a, int b)
{return b ? gcd(b, a % b) : a;
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t;cin >> t;while (t--){int x, y, z;cin >> x >> y >> z;int gc = gcd(x, y);if (z == 0 && x != 0 && y != 0){//z等于0且x，y里面没有0cout << "NO" << endl;continue;}if (z % gc == 0){cout << "YES" << endl;}else{cout << "NO" << endl;}}return 0;
}