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