GeezerVison is showing cpprefjp.github.io — std::gcd - cpprefjp C++日本語リファレンス
最終更新日時:
2026年09月20日 20時37分05秒 (JST)
rotarymars
が更新
function template
<numeric>
std:: gcd (C++17)
namespace std {
template < class M , class N >
constexpr common_type_t < M , N > gcd ( M m , N n );
}
概要
最大公約数 (greatest common divisor, gcd) を求める。
適格要件
型M および N が bool 以外の整数型であること
事前条件
|m| および |n| が common_type_t <M, N>
この条件により、gcd(m, m) == |m|が型Mの表現可能な値であることが保証される
戻り値
m と n が共に 0 の場合 0 を返すそれ以外の場合、引数 |m| と |n| の最大公約数を返す
例外
投げない。
例
基本的な使い方
#include <cassert>
#include <numeric>
int main () {
assert ( std::gcd ( 12 , 42 ) == 6 );
assert ( std::gcd ( 42 , 12 ) == 6 );
// コンパイル時に最大公約数を求めることもできる
static_assert ( std::gcd ( 0 , 0 ) == 0 );
static_assert ( std::gcd ( 3u , -7l ) == 1 );
}
出力
事前条件に違反する例
#include <iostream>
#include <numeric>
#include <cstdint>
#include <limits>
int main () {
// 符号付き整数型の最小値は、その絶対値を同じ型で表現できない。
// したがって以下の呼び出しは事前条件に違反しており、動作は未定義である
// (ある処理系では、符号付き整数型への変換によって負の値が返される)
using T = std::int32_t ;
constexpr auto m = std::numeric_limits < T >:: min ();
const auto gs = std::gcd < T , T > ( m , m ); // 未定義動作。|m| は int32_t で表現できない
std::cout << "gcd<int32_t, int32_t>(" << m << ", " << m << ") " << gs << std::endl ;
// 符号なし整数型であれば |m| を表現できるため、事前条件を満たす
using U = std::uint32_t ;
const auto gu = std::gcd < U , U > ( m , m );
std::cout << "gcd<uint32_t, uint32_t>(" << m << ", " << m << ") " << gu << std::endl ;
}
出力例
gcd<int32_t, int32_t>(-2147483648, -2147483648) -2147483648
gcd<uint32_t, uint32_t>(-2147483648, -2147483648) 2147483648
1行目は未定義動作 の結果であり、この値が得られることは保証されない。
3つ以上の値に対する最大公約数を求める
#include <cassert>
#include <numeric>
#include <vector>
// 可変引数で最大公約数を求める関数
template < class T >
T vgcd ( T m , T n ) {
return std::gcd ( m , n );
}
template < class T , class ... Args >
T vgcd ( T a , Args ... args ) {
return vgcd ( a , vgcd ( args ...));
}
int main () {
// 2つずつ最大公約数を求める
assert ( std::gcd ( std::gcd ( 12 , 42 ), 72 ) == 6 );
// リスト全体の最大公約数を求める
std::vector < int > v = { 12 , 42 , 72 };
int r = std::accumulate ( v.begin() , v.end() , 0 , []( int m , int n ) {
return std::gcd ( m , n );
});
assert ( r == 6 );
// 可変引数で最大公約数を求める
assert ( vgcd ( 12 , 42 , 72 ) == 6 );
}
出力
バージョン
言語
処理系
備考
Clang (libc++)
事前条件を満たすかどうかチェックしないが、戻り値を constexpr 指定するとオーバーフロー時にコンパイルエラーとなることがある。
事前条件を満たさない場合、オーバーフローにより戻り値が負になることがある。
GCC (libstdc++)
事前条件を満たすかどうかチェックしないが、戻り値を constexpr 指定するとオーバーフロー時にコンパイルエラーとなることがある。
事前条件を満たさない場合、オーバーフローにより戻り値が負になることがある。
参照
関連項目
実装例
$$ \mathrm{gcd}(m, n) = \begin{cases}
|m| & \text{if } n = 0 \\
\mathrm{gcd}(n, m \bmod n) & \text{otherwise}
\end{cases} $$
template < class M , class N >
constexpr std::common_type_t < M , N > gcd ( M m , N n ) {
if ( m == 0 && n == 0 ) {
return 0 ;
}
auto mm = abs ( m );
auto nn = abs ( n );
while ( mm != 0 && nn != 0 ) {
if ( mm > nn ) {
mm %= nn ;
}
else {
nn %= mm ;
}
}
return mm < nn ? nn : mm ;
}