最大公約数・最小公倍数
(math/euclidean-algorithm.hpp)

• View this file on GitHub
• Last update: 2021-04-15 20:33:39+09:00
• Include: #include "math/euclidean-algorithm.hpp"

Verified with

• test/aoj/NTL_1_C.test.cpp

Code

// @title 最大公約数・最小公倍数
#include <cassert>

using ll = long long;

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

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

#if 0
int main() {
  assert(gcd(18, 24) == 6);
  assert(lcm(18, 24) == 72);
  // aとbの順序が逆でもok
  assert(gcd(7, 3) == 1);
  // aとbの順序が逆でもok
  assert(lcm(7, 3) == 21);
  // intを超える範囲でも問題なく計算できる
  assert(gcd(123456789123456789, 987654321987654321) == 9000000009);
}
#endif

#line 1 "math/euclidean-algorithm.hpp"
// @title 最大公約数・最小公倍数
#include <cassert>

using ll = long long;

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

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

#if 0
int main() {
  assert(gcd(18, 24) == 6);
  assert(lcm(18, 24) == 72);
  // aとbの順序が逆でもok
  assert(gcd(7, 3) == 1);
  // aとbの順序が逆でもok
  assert(lcm(7, 3) == 21);
  // intを超える範囲でも問題なく計算できる
  assert(gcd(123456789123456789, 987654321987654321) == 9000000009);
}
#endif

Back to top page