最小公倍数・最大公約数

概要

最小公倍数(GCD)・最大公約数(LCM) を求める． gcd は algorithm ヘッダのビルトイン関数 __gcd でも代用可． 計算量はフィボナッチ数の逆関数 (のようなもの) で抑えられる．

計算量

$O(\log(\min(a,b)))$

実装

inline ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
inline ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }