1.11 最大公約数を求める。

2 整数の最大公約数を求めます。以下の条件を満たせば、必ずしも整数型でなくてもかまいません。

• 代入可能である
• < 演算子が使用可能
• % 演算子が使用可能

template<class T>
T gcd(T m, T n)
{
  if (m < T(0) || n < T(0))
  {
    return T(-1);
  }

  T r;
  while (T(0) < n)
  {
    r = m % n;
    m = n;
    n = r;
  }
  return m;
}

以下は、再帰を利用したメタ関数版です。

template<unsigned long M, unsigned long N>
struct tgcd
{
  static const unsigned int value = tgcd<N, M % N>::value;
};

template<unsigned long M>
struct tgcd<M, 0UL>
{
  static const unsigned long value = M;
};