Modular integer modulo \(N=2^{61}-1\), a Mersenne prime. More...

#include <mint2p61m1.hpp>

Public Types
using	mint = ModInt2P61M1

using	int_type = uint64_t

using	int_double_t = unsigned __int128

Public Member Functions
template<typename T , std::enable_if_t< std::is_integral_v< T > &&std::is_signed_v< T > > * = nullptr>
	ModInt2P61M1 (T x)
	Converts a plain integer to a Barrett modular integer.

template<typename T , std::enable_if_t< std::is_unsigned_v< T > > * = nullptr>
	ModInt2P61M1 (T x)
	Converts a plain integer to a Barrett modular integer.

int_type	val () const
	Converts back to a plain integer in the range \([0,N)\).

int_type	residue () const
	Returns a number that is the same for the same residue class modulo the modulus.

mint &	operator++ ()

mint	operator++ (int)

mint	operator+ () const

mint	operator+ (const mint &rhs) const

mint &	operator+= (const mint &rhs)

mint &	operator-- ()

mint	operator-- (int)

mint	operator- () const

mint	operator- (const mint &rhs) const

mint &	operator-= (const mint &rhs)

mint	operator* (const mint &rhs) const

mint &	*operator=** (const mint &rhs)

mint	inv () const

mint	operator/ (const mint &rhs) const

mint &	operator/= (const mint &rhs)

bool	operator== (const mint &rhs) const

bool	operator!= (const mint &rhs) const

Static Public Member Functions
static constexpr int_type	mod ()
	Returns the modulus.

Static Public Attributes
static constexpr int_type	MOD = (int_type(1) << 61) - 1

Detailed Description

Modular integer modulo \(N=2^{61}-1\), a Mersenne prime.

A large prime modulus with exceptionally fast multiplication, this is suitable for when the only requirement for the modulus is being sufficiently large. The most common use case is possibly rolling hash.

Constructor & Destructor Documentation

◆ ModInt2P61M1() [1/2]

template<typename T , std::enable_if_t< std::is_integral_v< T > &&std::is_signed_v< T > > * = nullptr>

cplib::ModInt2P61M1::ModInt2P61M1 ( T x )

inlineexplicit

Converts a plain integer to a Barrett modular integer.

This constructor is marked explicit because the cost of conversion is non-trivial (requires one Barrett reduction) and thus implicit conversion is discouraged.

◆ ModInt2P61M1() [2/2]

template<typename T , std::enable_if_t< std::is_unsigned_v< T > > * = nullptr>

cplib::ModInt2P61M1::ModInt2P61M1 ( T x )

inlineexplicit

Converts a plain integer to a Barrett modular integer.

This constructor is marked explicit because the cost of conversion is non-trivial (requires one Barrett reduction) and thus implicit conversion is discouraged.

Member Function Documentation

◆ residue()

int_type cplib::ModInt2P61M1::residue ( ) const

inline

Returns a number that is the same for the same residue class modulo the modulus.

This is the same as val(), unlike MontgomeryModInt.

The documentation for this class was generated from the following file:

src/cplib/num/mint2p61m1.hpp

cai_lw's competitive programming library

Public Types

Public Member Functions