数论模板

欧几里得算法（辗转相除法）

证明

欧几里得算法的核心为，将(a, b)（代表a与b的最大公约数）转化成(b, a % b)。

已知：若d能整除a且d能整除b，则d能整除a+b、a-b，也能整除ax+by。

证明(a, b) <==> (b, a % b)，需证明前面任意的公约数为后面的公约数，后面任意的公约数为前面的公约数。

a % b <==> a - a / b * b <==> a - c * b （c为常数）

所以(a, b) <==> (b, a - c * b)，由前面的条件，显然正确。

---

c++代码

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