misc/dynamic_modulo.hpp

• View this file on GitHub
• Last update: 2023-07-25 00:50:50+07:00
• Include: #include "misc/dynamic_modulo.hpp"

Code

#pragma once

struct dynamic_modulo {
  using Fp = dynamic_modulo;
  using i64 = int64_t;
  using u64 = uint64_t;
  using u128 = __uint128_t;

  static u64 mod;
  static u64 r;
  static u64 n2;

  static u64 get_r() {
    u64 ret = mod;
    for (i64 i = 0; i < 5; ++i) ret *= 2 - mod * ret;
    return ret;
  }
  static void set_mod(u64 m) {
    assert(m < (1LL << 62));
    assert((m & 1) == 1);
    mod = m;
    n2 = -u128(m) % m;
    r = get_r();
    assert(r * mod == 1);
  }
  u64 x;
  dynamic_modulo() : x(0) {}
  dynamic_modulo(const int64_t &b) : x(reduce((u128(b) + mod) * n2)){};
  static u64 reduce(const u128 &b) {
    return (b + u128(u64(b) * u64(-r)) * mod) >> 64;
  }
  Fp &operator+=(const Fp &b) {
    if (i64(x += b.x - 2 * mod) < 0) x += 2 * mod;
    return *this;
  }
  Fp &operator-=(const Fp &b) {
    if (i64(x -= b.x) < 0) x += 2 * mod;
    return *this;
  }
  Fp &operator*=(const Fp &b) {
    x = reduce(u128(x) * b.x);
    return *this;
  }
  Fp &operator/=(const Fp &b) {
    *this *= b.inv();
    return *this;
  }
  Fp operator+(const Fp &b) const { return Fp(*this) += b; }
  Fp operator-(const Fp &b) const { return Fp(*this) -= b; }
  Fp operator*(const Fp &b) const { return Fp(*this) *= b; }
  Fp operator/(const Fp &b) const { return Fp(*this) /= b; }
  bool operator==(const Fp &b) const {
    return (x >= mod ? x - mod : x) == (b.x >= mod ? b.x - mod : b.x);
  }
  bool operator!=(const Fp &b) const {
    return (x >= mod ? x - mod : x) != (b.x >= mod ? b.x - mod : b.x);
  }
  Fp operator-() const { return Fp() - Fp(*this); }
  Fp pow(u128 n) const {
    Fp ret(1), mul(*this);
    while (n > 0) {
      if (n & 1) ret *= mul;
      mul *= mul;
      n >>= 1;
    }
    return ret;
  }
  friend ostream &operator<<(ostream &os, const Fp &b) { return os << b.get(); }
  friend istream &operator>>(istream &is, Fp &b) {
    int64_t t;
    is >> t;
    b = dynamic_modulo(t);
    return (is);
  }
  Fp inv() const { return pow(mod - 2); }
  u64 get() const {
    u64 ret = reduce(x);
    return ret >= mod ? ret - mod : ret;
  }
  static u64 get_mod() { return mod; }
};
typename dynamic_modulo::u64 dynamic_modulo::mod, dynamic_modulo::r,
    dynamic_modulo::n2;

#line 2 "misc/dynamic_modulo.hpp"

struct dynamic_modulo {
  using Fp = dynamic_modulo;
  using i64 = int64_t;
  using u64 = uint64_t;
  using u128 = __uint128_t;

  static u64 mod;
  static u64 r;
  static u64 n2;

  static u64 get_r() {
    u64 ret = mod;
    for (i64 i = 0; i < 5; ++i) ret *= 2 - mod * ret;
    return ret;
  }
  static void set_mod(u64 m) {
    assert(m < (1LL << 62));
    assert((m & 1) == 1);
    mod = m;
    n2 = -u128(m) % m;
    r = get_r();
    assert(r * mod == 1);
  }
  u64 x;
  dynamic_modulo() : x(0) {}
  dynamic_modulo(const int64_t &b) : x(reduce((u128(b) + mod) * n2)){};
  static u64 reduce(const u128 &b) {
    return (b + u128(u64(b) * u64(-r)) * mod) >> 64;
  }
  Fp &operator+=(const Fp &b) {
    if (i64(x += b.x - 2 * mod) < 0) x += 2 * mod;
    return *this;
  }
  Fp &operator-=(const Fp &b) {
    if (i64(x -= b.x) < 0) x += 2 * mod;
    return *this;
  }
  Fp &operator*=(const Fp &b) {
    x = reduce(u128(x) * b.x);
    return *this;
  }
  Fp &operator/=(const Fp &b) {
    *this *= b.inv();
    return *this;
  }
  Fp operator+(const Fp &b) const { return Fp(*this) += b; }
  Fp operator-(const Fp &b) const { return Fp(*this) -= b; }
  Fp operator*(const Fp &b) const { return Fp(*this) *= b; }
  Fp operator/(const Fp &b) const { return Fp(*this) /= b; }
  bool operator==(const Fp &b) const {
    return (x >= mod ? x - mod : x) == (b.x >= mod ? b.x - mod : b.x);
  }
  bool operator!=(const Fp &b) const {
    return (x >= mod ? x - mod : x) != (b.x >= mod ? b.x - mod : b.x);
  }
  Fp operator-() const { return Fp() - Fp(*this); }
  Fp pow(u128 n) const {
    Fp ret(1), mul(*this);
    while (n > 0) {
      if (n & 1) ret *= mul;
      mul *= mul;
      n >>= 1;
    }
    return ret;
  }
  friend ostream &operator<<(ostream &os, const Fp &b) { return os << b.get(); }
  friend istream &operator>>(istream &is, Fp &b) {
    int64_t t;
    is >> t;
    b = dynamic_modulo(t);
    return (is);
  }
  Fp inv() const { return pow(mod - 2); }
  u64 get() const {
    u64 ret = reduce(x);
    return ret >= mod ? ret - mod : ret;
  }
  static u64 get_mod() { return mod; }
};
typename dynamic_modulo::u64 dynamic_modulo::mod, dynamic_modulo::r,
    dynamic_modulo::n2;

Back to top page