最大公約数・最小公倍数
最大公約数
ユークリッドの互除法を使おう。
code:最大公約数を求める
static inline long
gcd(long a, long b)
{
long k;
do {
k = a % b;
a = b;
b = k;
} while (k != 0);
return a;
}
C++ なら <numeric> にある std::gcd() も使える（C++17）。
最小公倍数
𝑎 × 𝑏 = lcm(𝑎, 𝑏) × gcd(𝑎, 𝑏) を利用する。
code:最小公倍数を求める
static inline long
lcm(long a, long b)
{
return a / gcd(a, b) * b;
}
C++ なら <numeric> にある std::lcm() も使える（C++17）。
このメモはもともと 2022-12-19 に書かれたものであるようです。