阿里云香港节点做的网站在哪个平台做推广比较好
G.Gcd
数论
题目大意
给定一个包含两个非负数的初始集合 S = { x , y } S=\{x,y\} S={x,y}
每次操作可以选定其中不相等的两个数 a , b a,b a,b ，并将 a − b a-b a−b 或 g c d ( a , b ) gcd(a,b) gcd(a,b) 置入集合 S S S ，其中 g c d ( 0 , a ) = a gcd(0,a)=a gcd(0,a)=a
可以操作任意次，问能否使得集合 S S S 包含非负数 z z z
前置知识点
裴蜀定理
解题思路
根据裴蜀定理，两个正整数辗转相减只能得到他们最大公约数的倍数//
因此对于 z z z ，判断其是否是 g c d ( x , y ) gcd(x,y) gcd(x,y) 的倍数即可
如果 z z z 是 g g g 的倍数，则可以通过以下操作得到 z z z ：
- 将 g = g c d ( x , y ) g=gcd(x,y) g=gcd(x,y) 置入集合
- x x x 作为 g g g 的倍数，其加减任意次 g g g 便可得到任意 g g g 的倍数。
只能减不能加怎么办呢//先把 x x x 减到 − g -g −g 就好了
值得注意的是，本题的数据约束为非负数，这意味着需要对 0 0 0 的情况进行特判//
- 对于 z = 0 z=0 z=0 ，仅当 x , y x,y x,y 有 0 0 0 时有解
- 对于 x = 0 x=0 x=0 或 y = 0 y=0 y=0 ，仅当 z z z 与其中之一相等时有解（实际上这条也满足裴蜀定理//只是懒得重写 g c d gcd gcd 了）
参考代码
参考代码为已AC代码主干，其中部分功能需读者自行实现
void solve()
{ll x,y,z;cin >> x >> y >> z;if(x&&y&&z==0) {cout << NO;return;}if((x==0)||(y==0)) if(z==x||z==y) {cout << YES;return;} else {cout << NO;return;}ll g=gcd(x,y);if(z%g) cout << NO;else cout << YES;
}