1.辗转相除法，用来求两个数的最大公约数

//普通的gcd
int gcd(int a, int b)
{
  if (b == 0)return a;
  return gcd(b, a % b);
}
//快速的gcd（我觉得好像也没多快）
int qGCD(int a, int b)
{
	if(a == 0) return b;
	if(b == 0) return a;
	if(!(a & 1) && !(b & 1)) // a % 2 == 0 && b % 2 == 0;
		return qGCD(a >> 1, b >> 1) << 1;
	else if(!(b & 1))
		return qGCD(a, b >> 1);
	else if(!(a & 1))
		return qGCD(a >> 1, b);
	else
		return qGCD(abs(a - b), min(a, b));
}

2.拓展欧里几德算法，用来求解ax+by=1的方程

int extgcd(int a, int b, int& x, int& y)
{
  int d = a;
  if (b != 0)
  {
    d = extgcd(b, a % b, y, x);
    y -= (a / b) * x;
  }
  else
  {
    x = 1;y = 0;
  }
  return d;
}