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