// Class Zm: Residue ring modulo m #ifndef ZM_H #define ZM_H 1 #include #include #include // Greatest Common Divizor (Euclid's Algorithm) int gcd(int m, int n); // Extended Euclid's Algorithm // Input: integer numbers m, n, one of them must be nonzero. // Output: d = gcd(m, n) and integers u, v such that // d = u*m + v*n void extEucl( int m, int n, int& d, int& u, int& v ); // Fast Power Algorithm int powermod(int a, int n, int m); class ZmException { private: const char *errorText; public: ZmException(const char* reason = ""): errorText(reason) {} const char* what() { return errorText; } }; class Zm { private: int n; static int m; public: static int mod() { return m; } static void setMod(int mmm) { m = abs(mmm); } // int k = Zm::mod(); // Zm::setMod(7); Zm(int x = 0): n(x%m) {} operator int() const { return n; } int number() const { return n; } int& number() { return n; } void setNumber(int k) { n = k%m; } Zm& operator+=(const Zm& k) { n = (n + k)%m; return *this; } Zm& operator-=(const Zm& k) { n = (n - k)%m; return *this; } Zm& operator*=(const Zm& k) { n = (n * k)%m; return *this; } Zm inverse() const { // y = x.inverse(); int d, u, v; extEucl(n, m, d, u, v); assert(d == u*n + v*m); if (d != 1) throw ZmException("Element is not invertible modulo m"); // 1 == u*n (mod m) return Zm(u); } Zm& operator/=(const Zm& k) { n *= k.inverse(); return *this; } Zm power(int e) const { int p = powermod(n, e, m); return Zm(p); } bool operator==(const Zm& k) const { return ((n - k)%m == 0); } bool operator!=(const Zm& k) const { return !operator==(k); } int residue() const { int r = n%m; if (r < 0) r += m; return r; } int signedResidue() const { int r = n%m; int m2 = m/2; if (r < (-m2)) r += m; else if ( r > m2 || (m%2 == 0 && r == m2) ) r -= m; return r; } bool operator<(const Zm& k) const { return (residue() < k.residue()); } bool operator<=(const Zm& k) const { return (residue() <= k.residue()); } bool operator>(const Zm& k) const { return !operator<=(k); } bool operator>=(const Zm& k) const { return !operator<(k); } }; inline Zm operator+(const Zm& a, const Zm& b) { Zm res = a; res += b; return res; } inline Zm operator-(const Zm& a, const Zm& b) { Zm res = a; res -= b; return res; } inline Zm operator*(const Zm& a, const Zm& b) { Zm res = a; res *= b; return res; } inline Zm operator/(const Zm& a, const Zm& b) { Zm res = a; res /= b; return res; } inline std::ostream& operator<<(std::ostream& s, const Zm& x) { //... s << int(x); s << x.signedResidue(); return s; } inline std::istream& operator>>(std::istream& s, Zm& x) { int k; s >> k; if (s.good()) x.setNumber(k); return s; } #endif /* defined ZM_H */