欧几里得算法

原理

  gcd可以计算两个数的最大公约数。欧几里得算法通过递归来计算最大公约数。基本情况是当b为0时，a和b的最大公约数就是a。

模板

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

扩展欧几里得算法