C++中如何高效求取最大公约数

C++中求取最大公约数有辗转相除法和更相减损术两种常用的方法。

辗转相除法

辗转相除法是求取最大公约数的一种经典算法，它的思想是：两个正整数a和b（a>b），它们的最大公约数等于a除以b的余数c和b之间的最大公约数。

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

以上是C++实现辗转相除法的一个简单示例，它的实现原理是先求出a和b的余数，用b除以余数，得到最大公约数。

更相减损术

更相减损术也是一种求取最大公约数的算法，它的思想是：两个正整数a和b（a>b），它们的最大公约数等于a和b中较小的数减去较大的数的差值c和较大的数之间的最大公约数。

int gcd(int a, int b) {
    if (a == b) return a;
    if (a > b) return gcd(a - b, b);
    return gcd(a, b - a);
}

以上是C++实现更相减损术的一个简单示例，它的实现原理是先求出a和b的差值，用较小的数减去差值，得到最大公约数。

以上就是C++中求取最大公约数的两种常用方法，辗转相除法和更相减损术，它们都是高效的算法，可以有效求取最大公约数。