G.Gcd

数论

题目大意

给定一个包含两个非负数的初始集合 $S=\{x,y\}S=\backslash \{x,y\backslash \}$ 每次操作可以选定其中不相等的两个数 $a,ba,b$ ，并将 $a-ba-b$ 或 $gcd(a,b)gcd(a,b)$ 置入集合 $SS$ ，其中 $gcd(0,a)=agcd(0,a)=a$ 可以操作任意次，问能否使得集合 $SS$ 包含非负数 $zz$

前置知识点

裴蜀定理

解题思路

根据裴蜀定理，两个正整数辗转相减只能得到他们最大公约数的倍数// 因此对于 $zz$ ，判断其是否是 $g=gcd(x,y)g=gcd(x,y)$ 的倍数即可。 如果 $zz$ 是 $gg$ 的倍数，则可以通过以下操作得到 $zz$ ：

1. 将 $g=gcd(x,y)g=gcd(x,y)$ 置入集合
2. $xx$ 作为 $gg$ 的倍数，其加减任意次 $gg$ 便可得到任意 $gg$ 的倍数。 只能减不能加怎么办呢//先把 $xx$ 减到 $-g-g$ 就好了

值得注意的是，本题的数据约束为非负数，这意味着需要对 $00$ 的情况进行特判//

1. 对于 $z=0z=0$ ，仅当 $x,yx,y$ 有 $00$ 时有解
2. 对于 $x=0x=0$ 或 $y=0y=0$ ，仅当 $zz$ 为非 $00$ 项的倍数时有解（实际上这条也满足裴蜀定理，直接归入一般情况即可）

*非常感谢牛客@南阳理工学院卢俊达的指正

参考样例：

in: 1 0 1 2
out: YES

参考代码

参考代码为已AC代码主干，其中部分功能需读者自行实现

void solve()
{
    ll x,y,z;
    cin >> x >> y >> z;
    if(x&&y&&z==0) {cout << NO;return;}
    ll g=gcd(x,y);
    if(z%g) cout << NO;
    else cout << YES;
}