Last active
October 21, 2021 03:32
-
-
Save buttercrab/1aafaed5ee67df6e374ac6603c14fb07 to your computer and use it in GitHub Desktop.
c++ field implementation for Problem Solving
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* @class field | |
* Number that is in modular Mod | |
* | |
* @tparam Mod should be prime number | |
*/ | |
template<long long Mod> | |
class field { | |
public: | |
template<long long N> | |
friend inline istream &operator>>(istream &in, field<N> &f); | |
template<long long N> | |
friend inline ostream &operator<<(ostream &out, const field<N> &f); | |
template<long long N, typename T> | |
friend inline bool operator==(const T &n, const field<N> &f); | |
template<long long N, typename T> | |
friend inline bool operator!=(const T &n, const field<N> &f); | |
template<long long N, typename T> | |
friend inline bool operator<(const T &n, const field<N> &f); | |
template<long long N, typename T> | |
friend inline bool operator>(const T &n, const field<N> &f); | |
template<long long N, typename T> | |
friend inline bool operator<=(const T &n, const field<N> &f); | |
template<long long N, typename T> | |
friend inline bool operator>=(const T &n, const field<N> &f); | |
template<typename T> | |
friend inline const field<Mod> &operator+(const T &n, const field<Mod> &f); | |
template<typename T> | |
friend inline const field<Mod> &operator-(const T &n, const field<Mod> &f); | |
template<typename T> | |
friend inline const field<Mod> &operator^(const T &n, const field<Mod> &f); | |
template<typename T> | |
friend inline const field<Mod> &operator*(const T &n, const field<Mod> &f); | |
template<typename T> | |
friend inline const field<Mod> &operator/(const T &n, const field<Mod> &f); | |
private: | |
long long d; | |
long long __pow(long long a, long long n) { | |
if (n < 0) return __pow(__pow(a, Mod - 2), -n); | |
long long res = 1; | |
while (n) { | |
if (n & 1) res = res * a % Mod; | |
a = a * a % Mod; | |
n >>= 1; | |
} | |
return res; | |
} | |
long long __pow(long long a, long long n) const { | |
if (n < 0) return __pow(__pow(a, Mod - 2), -n); | |
long long res = 1; | |
while (n) { | |
if (n & 1) res = res * a % Mod; | |
a = a * a % Mod; | |
n >>= 1; | |
} | |
return res; | |
} | |
public: | |
field() : d() {} | |
explicit field(const bool &n) : d(n % Mod) {} | |
explicit field(const char &n) : d(n % Mod) {} | |
explicit field(const short &n) : d(n % Mod) {} | |
explicit field(const int &n) : d(n % Mod) {} | |
explicit field(const long &n) : d(n % Mod) {} | |
explicit field(const long long &n) : d(n % Mod) {} | |
explicit field(const unsigned char &n) : d(n % Mod) {} | |
explicit field(const unsigned short &n) : d(n % Mod) {} | |
explicit field(const unsigned int &n) : d(n % Mod) {} | |
explicit field(const unsigned long &n) : d(n % Mod) {} | |
explicit field(const unsigned long long &n) : d(n % Mod) {} | |
field(const field<Mod> &f) : d(f.d) {} | |
field(field<Mod> &&f) noexcept: d(f.d) {} | |
field<Mod> &operator=(const char &n) { | |
d = n % Mod; | |
return *this; | |
} | |
field<Mod> &operator=(const short &n) { | |
d = n % Mod; | |
return *this; | |
} | |
field<Mod> &operator=(const int &n) { | |
d = n % Mod; | |
return *this; | |
} | |
field<Mod> &operator=(const long &n) { | |
d = n % Mod; | |
return *this; | |
} | |
field<Mod> &operator=(const long long &n) { | |
d = n % Mod; | |
return *this; | |
} | |
field<Mod> &operator=(const unsigned char &n) { | |
d = n % Mod; | |
return *this; | |
} | |
field<Mod> &operator=(const unsigned short &n) { | |
d = n % Mod; | |
return *this; | |
} | |
field<Mod> &operator=(const unsigned int &n) { | |
d = n % Mod; | |
return *this; | |
} | |
field<Mod> &operator=(const unsigned long &n) { | |
d = n % Mod; | |
return *this; | |
} | |
field<Mod> &operator=(const unsigned long long &n) { | |
d = n % Mod; | |
return *this; | |
} | |
field<Mod> &operator=(const field<Mod> &f) { | |
d = f.d; | |
return *this; | |
} | |
field<Mod> &operator=(field<Mod> &&f) noexcept { | |
d = f.d; | |
return *this; | |
} | |
explicit operator bool() const { return (bool) d; } | |
explicit operator char() const { return (char) d; } | |
explicit operator short() const { return (short) d; } | |
explicit operator int() const { return (int) d; } | |
explicit operator long() const { return (long) d; } | |
explicit operator long long() const { return d; } | |
explicit operator unsigned char() const { return (unsigned char) d; } | |
explicit operator unsigned short() const { return (unsigned short) d; } | |
explicit operator unsigned int() const { return (unsigned int) d; } | |
explicit operator unsigned long() const { return (unsigned long) d; } | |
explicit operator unsigned long long() const { return (unsigned long long) d; } | |
template<typename T> | |
inline field<Mod> operator+(const T &n) { return field<Mod>((d + n % Mod) % Mod); } | |
inline field<Mod> operator+(const field<Mod> &f) { return field<Mod>((d + f.d) % Mod); } | |
template<typename T> | |
inline field<Mod> operator-(const T &n) { return field<Mod>((d - n % Mod + Mod) % Mod); } | |
inline field<Mod> operator-(const field<Mod> &f) { return field<Mod>((d - f.d + Mod) % Mod); } | |
template<typename T> | |
inline field<Mod> operator^(const T &n) { return field<Mod>(__pow(d, n)); } | |
inline field<Mod> operator^(const field<Mod> &f) { return field<Mod>(__pow(d, f.d)); } | |
template<typename T> | |
inline field<Mod> operator*(const T &n) { return field<Mod>(d * (n % Mod) % Mod); } | |
inline field<Mod> operator*(const field<Mod> &f) { return field<Mod>(d * f.d % Mod); } | |
template<typename T> | |
inline field<Mod> operator/(const T &n) { return (*this) / (field<Mod>(n)); } | |
inline field<Mod> operator/(const field<Mod> &f) { return (*this) * (!f); } | |
inline field<Mod> operator!() { return field<Mod>(__pow(d, Mod - 2)); } | |
inline field<Mod> operator++() { return (*this) += 1; } | |
inline const field<Mod> operator++(int) { | |
auto t = (*this); | |
++(*this); | |
return t; | |
} | |
inline field<Mod> operator--() { return (*this) -= 1; } | |
inline const field<Mod> operator--(int) { | |
auto t = (*this); | |
--(*this); | |
return t; | |
} | |
template<typename T> | |
inline field<Mod> operator+(const T &n) const { return field<Mod>((d + n % Mod) % Mod); } | |
inline field<Mod> operator+(const field<Mod> &f) const { return field<Mod>((d + f.d) % Mod); } | |
template<typename T> | |
inline field<Mod> operator-(const T &n) const { return field<Mod>((d - n % Mod + Mod) % Mod); } | |
inline field<Mod> operator-(const field<Mod> &f) const { return field<Mod>((d - f.d + Mod) % Mod); } | |
template<typename T> | |
inline field<Mod> operator^(const T &n) const { return field<Mod>(__pow(d, n)); } | |
inline field<Mod> operator^(const field<Mod> &f) const { return field<Mod>(__pow(d, f.d)); } | |
template<typename T> | |
inline field<Mod> operator*(const T &n) const { return field<Mod>(d * (n % Mod) % Mod); } | |
inline field<Mod> operator*(const field<Mod> &f) const { return field<Mod>(d * f.d % Mod); } | |
template<typename T> | |
inline field<Mod> operator/(const T &n) const { return (*this) / (field<Mod>(n)); } | |
inline field<Mod> operator/(const field<Mod> &f) const { return (*this) * (!f); } | |
inline field<Mod> operator!() const { return field<Mod>(__pow(d, Mod - 2)); } | |
inline field<Mod> operator++() const { return (*this) += 1; } | |
inline const field<Mod> operator++(int) const { | |
auto t = (*this); | |
++(*this); | |
return t; | |
} | |
inline field<Mod> operator--() const { return (*this) -= 1; } | |
inline const field<Mod> operator--(int) const { | |
auto t = (*this); | |
--(*this); | |
return t; | |
} | |
template<typename T> | |
inline field<Mod> &operator+=(const T &n) { | |
(*this) = (*this) + n; | |
return (*this); | |
} | |
inline field<Mod> &operator+=(const field<Mod> &f) { | |
(*this) = (*this) + f.d; | |
return (*this); | |
} | |
template<typename T> | |
inline field<Mod> &operator-=(const T &n) { | |
(*this) = (*this) - n; | |
return (*this); | |
} | |
inline field<Mod> &operator-=(const field<Mod> &f) { | |
(*this) = (*this) - f.d; | |
return (*this); | |
} | |
template<typename T> | |
inline field<Mod> &operator^=(const T &n) { | |
(*this) = (*this) ^ n; | |
return (*this); | |
} | |
inline field<Mod> &operator^=(const field<Mod> &f) { | |
(*this) = (*this) ^ f.d; | |
return (*this); | |
} | |
template<typename T> | |
inline field<Mod> &operator*=(const T &n) { | |
(*this) = (*this) * n; | |
return (*this); | |
} | |
inline field<Mod> &operator*=(const field<Mod> &f) { | |
(*this) = (*this) * f.d; | |
return (*this); | |
} | |
template<typename T> | |
inline field<Mod> &operator/=(const T &n) { | |
(*this) = (*this) / n; | |
return (*this); | |
} | |
inline field<Mod> &operator/=(const field<Mod> &f) { | |
(*this) = (*this) / f.d; | |
return (*this); | |
} | |
template<typename T> | |
inline const field<Mod> &operator+=(const T &n) const { | |
(*this) = (*this) + n; | |
return (*this); | |
} | |
inline const field<Mod> &operator+=(const field<Mod> &f) const { | |
(*this) = (*this) + f.d; | |
return (*this); | |
} | |
template<typename T> | |
inline const field<Mod> &operator-=(const T &n) const { | |
(*this) = (*this) - n; | |
return (*this); | |
} | |
inline const field<Mod> &operator-=(const field<Mod> &f) const { | |
(*this) = (*this) - f.d; | |
return (*this); | |
} | |
template<typename T> | |
inline const field<Mod> &operator^=(const T &n) const { | |
(*this) = (*this) ^ n; | |
return (*this); | |
} | |
inline const field<Mod> &operator^=(const field<Mod> &f) const { | |
(*this) = (*this) ^ f.d; | |
return (*this); | |
} | |
template<typename T> | |
inline const field<Mod> &operator*=(const T &n) const { | |
(*this) = (*this) * n; | |
return (*this); | |
} | |
inline const field<Mod> &operator*=(const field<Mod> &f) const { | |
(*this) = (*this) * f.d; | |
return (*this); | |
} | |
template<typename T> | |
inline const field<Mod> &operator/=(const T &n) const { | |
(*this) = (*this) / n; | |
return (*this); | |
} | |
inline const field<Mod> &operator/=(const field<Mod> &f) const { | |
(*this) = (*this) / f.d; | |
return (*this); | |
} | |
template<typename T> | |
inline bool operator==(const T &n) { return static_cast<T>(d) == n; } | |
inline bool operator==(const field<Mod> &f) { return d == f.d; } | |
template<typename T> | |
inline bool operator!=(const T &n) { return static_cast<T>(d) != n; } | |
inline bool operator!=(const field<Mod> &f) { return d != f.d; } | |
template<typename T> | |
inline bool operator<(const T &n) { return static_cast<T>(d) < n; } | |
inline bool operator<(const field<Mod> &f) { return d < f.d; } | |
template<typename T> | |
inline bool operator>(const T &n) { return static_cast<T>(d) > n; } | |
inline bool operator>(const field<Mod> &f) { return d > f.d; } | |
template<typename T> | |
inline bool operator<=(const T &n) { return static_cast<T>(d) <= n; } | |
inline bool operator<=(const field<Mod> &f) { return d <= f.d; } | |
template<typename T> | |
inline bool operator>=(const T &n) { return static_cast<T>(d) >= n; } | |
inline bool operator>=(const field<Mod> &f) { return d >= f.d; } | |
template<typename T> | |
inline bool operator==(const T &n) const { return static_cast<T>(d) == n; } | |
inline bool operator==(const field<Mod> &f) const { return d == f.d; } | |
template<typename T> | |
inline bool operator!=(const T &n) const { return static_cast<T>(d) != n; } | |
inline bool operator!=(const field<Mod> &f) const { return d != f.d; } | |
template<typename T> | |
inline bool operator<(const T &n) const { return static_cast<T>(d) < n; } | |
inline bool operator<(const field<Mod> &f) const { return d < f.d; } | |
template<typename T> | |
inline bool operator>(const T &n) const { return static_cast<T>(d) > n; } | |
inline bool operator>(const field<Mod> &f) const { return d > f.d; } | |
template<typename T> | |
inline bool operator<=(const T &n) const { return static_cast<T>(d) <= n; } | |
inline bool operator<=(const field<Mod> &f) const { return d <= f.d; } | |
template<typename T> | |
inline bool operator>=(const T &n) const { return static_cast<T>(d) >= n; } | |
inline bool operator>=(const field<Mod> &f) const { return d >= f.d; } | |
}; | |
template<long long N> | |
inline istream &operator>>(istream &in, field<N> &f) { | |
in >> f.d; | |
f.d %= N; | |
return in; | |
} | |
template<long long N> | |
inline ostream &operator<<(ostream &out, const field<N> &f) { return out << f.d; } | |
template<long long Mod, typename T> | |
inline const field<Mod> &operator+(const T &n, const field<Mod> &f) { return f + n; } | |
template<long long Mod, typename T> | |
inline const field<Mod> &operator-(const T &n, const field<Mod> &f) { return field<Mod>((n % Mod - f.d + Mod) % Mod); } | |
template<long long Mod, typename T> | |
inline const field<Mod> &operator^(const T &n, const field<Mod> &f) { return field<Mod>(n) ^ f; } | |
template<long long Mod, typename T> | |
inline const field<Mod> &operator*(const T &n, const field<Mod> &f) { return f * n; } | |
template<long long Mod, typename T> | |
inline const field<Mod> &operator/(const T &n, const field<Mod> &f) { return !f * n; } | |
template<long long N, typename T> | |
inline bool operator==(const T &n, const field<N> &f) { return n == f.d; } | |
template<long long N, typename T> | |
inline bool operator!=(const T &n, const field<N> &f) { return n != f.d; } | |
template<long long N, typename T> | |
inline bool operator<(const T &n, const field<N> &f) { return n < f.d; } | |
template<long long N, typename T> | |
inline bool operator>(const T &n, const field<N> &f) { return n > f.d; } | |
template<long long N, typename T> | |
inline bool operator<=(const T &n, const field<N> &f) { return n <= f.d; } | |
template<long long N, typename T> | |
inline bool operator>=(const T &n, const field<N> &f) { return n >= f.d; } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment