gcd

関数 · 整数ユーティリティ

std::int64_t gcd(const std::vector<std::int64_t> &v);

概要

整数列の最大公約数を返す

計算量

• 要素数を $n$、絶対値の最大を $M$ として $O(n\log M)$

関連項目

• lcm — 整数列の最小公倍数を返す
• floor_div — $\lfloor p/q\rfloor$ を返す
• ceil_div — $\lceil p/q\rceil$ を返す
• checked_pow — オーバーフローを検出する累乗