引言
有时需要求两数（\(a,b\)）的最大公约数，即 \(\gcd(a,b)\)。
那怎么求？
原理
设 \(g=\gcd(a,b),a 那么 \(a\) 是 \(g\) 的倍数，\(b\) 也是 \(g\) 的倍数，那么 \(m=b\bmod a=b-ka\) 也是 \(g\) 的倍数（\(k\) 是某个合适的整数，使 \(0\le m \(\because ka+m=b\) \(\therefore\) 只要 \(a,m\) 是 \(g\) 的倍数，那么 \(b\) 也一定是 \(g\) 的倍数。 问题就转化为求 \(\gcd(m,a)=\gcd(b\bmod a,a)\)。由于 \(m\) 是模 \(a\) 的余数，所以 \(m （说的不清楚请直接在评论区吐槽。） 最后如果 \(a=0\)，返回 \(b\)。 实现 inline int gcd(int a,int b) { return (a?gcd(b%a,a):b);//等价于 return (b?gcd(a,a%b):a); } ll gcd(ll x,ll y) { if(!x)return y; if(!y)return x; int xz=__builtin_ctzll(x),yz=__builtin_ctzll(y),sh=std::min(xz,yz); x>>=xz,y>>=yz; while(true) { if(y>x)std::swap(x,y); x-=y; if(!x)break; x>>=__builtin_ctzll(x); } return y< }