辗转相除法

用处

求出 a 、 b 两个整数间的最大公因数

原理

由于这个算法涉及到数论，我们使用几何图形来展示原理：

步骤一

我们假设 a 、 b 分别对应长方形的长、宽

步骤二

每一次操作，取出 n 个短边长的正方形填充长方形

这次操作后，新的长方形的长、宽分别为 \(b\) 、 \(a \bmod b\)

步骤三

\[\begin{aligned}a \bmod b = r_1 \end{aligned} \]

这次操作后，新的长方形的长、宽分别为 \(r1\) 、 \(b \bmod r1\)

步骤四

\[\begin{aligned}b \bmod r_1 = r_2 \end{aligned} \]

这次操作后，新的长方形的长、宽分别为 \(r2\) 、 \(r1 \bmod r2\)

步骤...

一直重复此操作，直至正方形可以将长方形完全填充，此时正方形的边长就是所求最大公约数

实现

该算法通常有两种实现方式，分别为递归法与迭代法

递归

template <typename T, typename U> constexpr auto gcd(const T &_a, const U &_b) -> typename std::common_type_t<T, U>
{using RT = std::common_type_t<T, U>;auto a = _a >= 0 ? static_cast<RT>(_a) : static_cast<RT>(-_a);auto b = _b >= 0 ? static_cast<RT>(_b) : static_cast<RT>(-_b);if (b == 0)return a;return gcd(b, a % b);
}

迭代

template <typename T, typename U> constexpr auto gcd(const T &_a, const U &_b) -> typename std::common_type_t<T, U>
{using RT = std::common_type_t<T, U>;auto a = _a >= 0 ? static_cast<RT>(_a) : static_cast<RT>(-_a);auto b = _b >= 0 ? static_cast<RT>(_b) : static_cast<RT>(-_b);while (b != 0){RT temp = b;b = a % b;a = temp;}return a;
}