zmodn.h (2052B)
1 #ifndef ZMODN_H 2 #define ZMODN_H 3 4 #include <cstdint> 5 #include <iostream> 6 #include <optional> 7 #include <tuple> 8 #include <type_traits> 9 10 template<typename T> 11 concept Integer = requires(T a, T b, int i, std::ostream& os) { 12 {T(i)}; 13 14 {a + b} -> std::same_as<T>; 15 {a - b} -> std::same_as<T>; 16 {a * b} -> std::same_as<T>; 17 {a / b} -> std::same_as<T>; 18 {a % b} -> std::same_as<T>; 19 20 {a == b} -> std::same_as<bool>; 21 {a != b} -> std::same_as<bool>; 22 23 {os << a} -> std::same_as<std::ostream&>; 24 }; 25 26 template<Integer T> 27 std::tuple<T, T, T> extended_gcd(T a, T b) { 28 if (b == 0) return {a, 1, 0}; 29 auto [g, x, y] = extended_gcd(b, a%b); 30 return {g, y, x - y*(a/b)}; 31 } 32 33 template<Integer auto N> 34 requires(N > 1) 35 class Zmod { 36 public: 37 Zmod(decltype(N) z) : value{(z%N + N) % N} {} 38 decltype(N) toint() const { return value; } 39 40 Zmod operator+(const Zmod& z) const { return value + z.value; } 41 Zmod operator-(const Zmod& z) const { return value - z.value; } 42 Zmod operator*(const Zmod& z) const { return value * z.value; } 43 44 Zmod operator+=(const Zmod& z) { return (*this) = value + z.value; } 45 Zmod operator-=(const Zmod& z) { return (*this) = value - z.value; } 46 Zmod operator*=(const Zmod& z) { return (*this) = value * z.value; } 47 48 Zmod operator^(decltype(N) z) const { 49 if (z == 0) return 1; 50 if (z % 2 == 0) return (((*this) * (*this)) ^ (z/2)); 51 return (*this) * ((*this) ^ (z-1)); 52 } 53 54 bool operator==(const Zmod& z) const { return value == z.value; } 55 bool operator!=(const Zmod& z) const { return value != z.value; } 56 57 std::optional<Zmod> inverse() const { 58 auto [g, a, _] = extended_gcd(value, N); 59 return g == 1 ? Zmod(a) : std::optional<Zmod>{}; 60 } 61 62 std::optional<Zmod> operator/(const Zmod& d) const { 63 auto i = d.inverse(); 64 return i ? (*this) * i.value() : i; 65 } 66 67 std::optional<Zmod> operator/=(const Zmod& d) { 68 auto q = *this / d; 69 return q ? (*this = q.value()) : q; 70 } 71 72 friend std::ostream& operator<<(std::ostream& os, const Zmod<N>& z) { 73 return os << "(" << z.value << " mod " << N << ")"; 74 } 75 private: 76 decltype(N) value; 77 }; 78 79 #endif