辗转相除法，是在$O(\log{min(a,b)} )$的复杂度求解两数最大公约数的方法
原理
对于整数$a$，$b$，记符号$(a,b)$为$a$与$b$的最大公约数。
形式化的：
$$ (a,b) = \max_{d|a \wedge d|b , d \in N^*}{d} $$
以后若未加特殊说明，其中为正整数且返回一个正整数的该符号皆默认为该定义
核心原理：
存在递归式
$$ (a,b)=(a-b,b) $$
成立
证：设$(a,b)=x,(a-b,b)=y$,容易发现$x\ge y,y\ge x$，即$x=y$
证毕
那么
$$ (a,b)=(a+kb,b)(k\in \mathbb{Z}) $$
也成立
代码
int gcd(int a,int b){
return !b ? a : gcd(b, a % b);
}