辗转相除法和更相减损术

高中学过的求大公约数的方法就是辗转相除法和更相减损术了。

辗转相除法递归版

#include <iostream>
using std::cin;
using std::cout;
using std::endl;

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

int main() {
  int n, m;
  cin >> n >> m;
  cout << gcd(n, m) << endl;
  return 0;
}

非递归

#include <iostream>
using std::cin;
using std::cout;
using std::endl;

int gcd(int a, int b) {
  int temp;
  while (b > 0) {
    temp = a % b;
    a = b;
    b = temp;
  }
  return a;
}

int main() {
  int n, m;
  cin >> n >> m;
  cout << gcd(n, m) << endl;
  return 0;
}

更相减损术

#include <iostream>
using std::cin;
using std::cout;
using std::endl;

int main() {
  int a, b;
  cin >> a >> b;
  while (a != b) {
    if (a > b) {
      a -= b;
    } else {
      b -= a;
    }
  }
  cout << a << endl;
  return 0;
}

比较：
更相减损术和辗转相除法的主要区别在于前者所使用的运算是“减”，后者是“除”。从算法思想上看，两者并没有本质上的区别，但是在计算过程中，如果遇到一个数很大，另一个数比较小的情况，可能要进行很多次减法才能达到一次除法的效果，从而使得算法的时间复杂度退化为O(N)，其中N是原先的两个数中较大的一个。相比之下，辗转相除法的时间复杂度稳定于O(logN)。