JZTXT

欧几里得算法

发布时间 2023-04-06 19:51:58作者: luogu_wsy0704

欧几里得算法(Euclid)

最大公约数

\(gcd(a, b)\)

int gcd (int a, int b) {
  while (b) {
    swap(a, b);
    b %= a;
  }
  return a;
}

//---or---

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

最小公倍数

\(lcm(a, b)\)

int lcm (int a, int b) {
  int x = a * b;
  while (b) {
    swap(a, b);
    b %= a;
  }
  return x / a;
}

//---or---

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

int lcm (int a, int b) {
  return a * b / gcd(a, b);
}