// Field.h.
//
// Contents:   Template class Z for modular integers.
//
//             For a positive int m, Z<m> is a class type whose
//             objects are integers modulo m.  The int m must be a
//             compile-time constant.  At present, the code may work
//             correctly only if m*m < INT_MAX. When m is prime, the
//             integers modulo m form a field.
//

#ifndef FIELD_DEFINED
#define FIELD_DEFINED

#include <cstdlib>
#include "field_traits.h"

// Function to return multiplicative inverse of n modulo m.  Returns 0 if
//   gcd(m,n) > 1.  Both numbers must be nonnegative even though the type is int.

inline unsigned invMod( int m, int n)
{
   if ( n == 0 )
      return 0;
   int b = 1, bpr = 0, c = m, d = n, t;
   ldiv_t L;
   while ( L = ldiv(c,d) , L.rem != 0 ) {
      c = d;
      d = L.rem;
      t = bpr;
      bpr = b;
      b = t - L.quot * b;
   }
   if ( d == 1 )
      return (b < 0) ? (b + m) : b;
   else
      return 0;
}

// Template class Z<m> for integers modulo m.
template<int m>
class Z;

template<int m>
struct Field_traits<Z<m> > {
   typedef arith_exact arith_type;
};

template< int m>
class Z {
private:
   int n;                   // 0 <= n < m.
   struct nocheck{};
   Z( int k, nocheck) : n(k) {}

public:

   // Constructor.
   Z( int k = 0) : n( (k < 0) ? (m - 1 - (-k-1) % m) : (k < m) ? (k) : (k % m) ) {}

   // Non-implicit conversion to int, and implicit conversion to bool.
   int asInt() const { return n;}
   operator bool() const { return n != 0;}

   // Unary minus and multiplicative inverse.
   Z operator-() const { return Z( (n>0 ? m-n : 0), nocheck());}
   Z inverse() const {
      int i = invMod(m,n);  if (i == 0) throw "inversion error"; return Z( i, nocheck());
   }
   bool isInvertible() const { return invMod(m,n) != 0;}

   // Equality and inequality.
   friend bool operator==( Z<m> a, Z<m> b) { return a.n == b.n;}
   friend bool operator!=( Z<m> a, Z<m> b) { return a.n != b.n;}

   // Compound assignment.
   Z &operator+=( Z b) { n += b.n; if (n >= m) n -= m; return *this;}
   Z &operator-=( Z b) { n += m; n -= b.n; if (n >= m) n -= m; return *this;}
   Z &operator*=( Z b) { n *= b.n; n %= m; return *this;}
   Z &operator/=( Z b) { return *this *= b.inverse();}

   // Binary arithmetic operators.
   friend Z<m> operator+( Z<m> a, Z<m> b) { int s = a.n + b.n; return (s < m) ? Z<m>(s,nocheck())
                                                                     : Z<m>(s-m,nocheck());}
   friend Z<m> operator-( Z<m> a, Z<m> b) { int d = a.n - b.n; return (d < 0) ? Z<m>(d+m,nocheck())
                                                                     :  Z<m>(d);}
   friend Z<m> operator * ( const Z &a, const Z &b) { return Z<m>( a.n * b.n % m, nocheck());}
   friend Z<m> operator / ( const Z &a, const Z &b) { return a * b.inverse();}
};

// Explicit specialization of template class Z<m> for integers modulo 2.
template<>
class Z<2> {
private:
   int n;                   // 0 <= n < 2.

public:

   // Constructor.
   Z( int k = 0) : n( k & 1) {}

   // Non-implicit conversion to int.
   int asInt() const { return n;}

   // Unary minus and multiplicative inverse.
   Z operator-() const { return *this;}
   Z inverse() const { if (n == 0) throw "inversion error"; return *this;}
   bool isInvertible() const { return n != 0;}

   // Equality and inequality.
   friend bool operator==( Z<2> a, Z<2> b) { return a.n == b.n;}
   friend bool operator!=( Z<2> a, Z<2> b) { return a.n != b.n;}

   // Compound assignment.
   Z &operator+=( Z b) { n ^= b.n; return *this;}
   Z &operator-=( Z b) { n ^= b.n; return *this;}
   Z &operator*=( Z b) { n &= b.n; return *this;}
   Z &operator/=( Z b) { return *this *= b.inverse();}

   // Binary arithmetic operators.
   friend Z<2> operator+( Z<2> a, Z<2> b) { return Z<2>(a.n ^ b.n);}
   friend Z<2> operator-( Z<2> a, Z<2> b) { return Z<2>(a.n ^ b.n);}
   friend Z<2> operator*( Z<2> a, Z<2> b) { return Z<2>(a.n & b.n);}
   friend Z<2> operator/( Z<2> a, Z<2> b) { return a * b.inverse();}
};

// Explicit specialization of member function inverse() and isInvertible() for z = 3.
template<>
inline Z<3> Z<3>::inverse() const { if (n == 0) throw "inversion error"; return *this;}

template<>
inline bool Z<3>::isInvertible() const { return n != 0;}

// Input/output
template< int m>
istream &operator>>( istream &is, Z<m> &b) {
   int k; is >> k; if (is) b = Z<m>(k); return is;
}

template<int m>
ostream &operator<<( ostream &os, Z<m> b) {
   return os << b.asInt();
}

#endif