zmodn-4.cpp (1682B)
1 #include "bigint.h" 2 3 #include <iostream> 4 #include <optional> 5 #include <tuple> 6 #include <type_traits> 7 8 template<typename T> 9 concept Integer = requires(T a, T b, int i) { 10 {T(i)}; 11 12 {a + b} -> std::same_as<T>; 13 {a - b} -> std::same_as<T>; 14 {a * b} -> std::same_as<T>; 15 {a / b} -> std::same_as<T>; 16 {a % b} -> std::same_as<T>; 17 18 {a == b} -> std::same_as<bool>; 19 {a != b} -> std::same_as<bool>; 20 }; 21 22 template<Integer T> 23 std::tuple<T, T, T> extended_gcd(T a, T b) { 24 if (b == 0) return {a, 1, 0}; 25 auto [g, x, y] = extended_gcd(b, a%b); 26 return {g, y, x - y*(a/b)}; 27 } 28 29 template<Integer auto N> 30 requires (N > 1) 31 class Zmod { 32 public: 33 decltype(N) value; 34 35 Zmod(decltype(N) z) : value{(z%N + N) % N} {} 36 37 Zmod operator+(const Zmod& z) const { return value + z.value; } 38 Zmod operator-(const Zmod& z) const { return value - z.value; } 39 Zmod operator*(const Zmod& z) const { return value * z.value; } 40 41 std::optional<Zmod> inverse() const { 42 auto [g, a, _] = extended_gcd(value, N); 43 return g == 1 ? Zmod(a) : std::optional<Zmod>{}; 44 } 45 46 std::optional<Zmod> operator/(const Zmod& d) const { 47 auto i = d.inverse(); 48 return i ? (*this) * i.value() : i; 49 } 50 51 std::optional<Zmod> operator/=(const Zmod& d) { 52 auto q = *this / d; 53 return q ? (*this = q.value()) : q; 54 } 55 }; 56 57 int main() { 58 constexpr BigInt N("1000000000000000000000000000000"); 59 Zmod<N> x(BigInt("123456781234567812345678")); 60 Zmod<N> y(BigInt("987654321987654321")); 61 62 std::cout << x.value << " * " 63 << y.value << " (mod " << N << ") = " 64 << (x * y).value << std::endl; 65 66 // The following line gives an error when trying to specialize Zmod<M> 67 // constexpr double M = 3.14; 68 // Zmod<M> z(4); 69 70 return 0; 71 }