|
cai_lw's competitive programming library
|
|
| |
|
cai_lw's competitive programming library
|
|
|
| |
Modular integer stored in Montgomery form. More...
#include <mmint.hpp>
Public Types | |
| using | mint = MontgomeryModInt |
| using | int_type = typename Context::int_type |
| using | mr_type = typename Context::mr_type |
| using | int_double_t = typename mr_type::int_double_t |
Public Member Functions | |
| template<typename T , std::enable_if_t< std::is_integral_v< T > &&std::is_signed_v< T > > * = nullptr> | |
| MontgomeryModInt (T x) | |
| Converts a plain integer to a Montgomery modular integer. | |
| template<typename T , std::enable_if_t< std::is_unsigned_v< T > > * = nullptr> | |
| MontgomeryModInt (T x) | |
| Converts a plain integer to a Montgomery 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 |
| Returns the modular inverse. | |
| 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 Guard | set_mod_guard (int_type mod) |
| Set the dynamic modint's modulus. | |
| static constexpr int_type | mod () |
| Returns the modulus. | |
Related Functions | |
(Note that these are not member functions.) | |
| template<uint32_t Mod> | |
| using | MMInt = MontgomeryModInt< impl::StaticMontgomeryReductionContext< uint32_t, Mod > > |
| Type alias for 32-bit MontgomeryModInt with compile-time constant modulus. | |
| template<uint64_t Mod> | |
| using | MMInt64 = MontgomeryModInt< impl::StaticMontgomeryReductionContext< uint64_t, Mod > > |
| Type alias for 64-bit MontgomeryModInt with compile-time constant modulus. | |
| using | DynamicMMInt30 = MontgomeryModInt< impl::DynamicMontgomeryReductionContext< uint32_t, true > > |
| Type alias for dynamic MontgomeryModInt with modulus less than \(2^{30}\). | |
| using | DynamicMMInt32 = MontgomeryModInt< impl::DynamicMontgomeryReductionContext< uint32_t, false > > |
| Type alias for dynamic MontgomeryModInt with modulus less than \(2^{32}\). | |
| using | DynamicMMInt62 = MontgomeryModInt< impl::DynamicMontgomeryReductionContext< uint64_t, true > > |
| Type alias for dynamic MontgomeryModInt with modulus less than \(2^{62}\). | |
| using | DynamicMMInt64 = MontgomeryModInt< impl::DynamicMontgomeryReductionContext< uint64_t, false > > |
| Type alias for dynamic MontgomeryModInt with modulus less than \(2^{64}\). | |
| template<typename Visitor , typename UInt , typename... Args> | |
| auto | mmint_by_modulus (Visitor &&visitor, UInt mod, Args &&... args) |
| Given a modulus, calls a callable (visitor) with a dynamically selected fastest MontgomeryModInt type. | |
Modular integer stored in Montgomery form.
Your code should generally use the type alias MMInt or MMInt64 for compile-time static modulus, or one of DynamicMMInt30, DynamicMMInt32, DynamicMMInt62, DynamicMMInt64 for runtime dynamic modulus.
Unless converting between modular integers and ordinary integers very frequently (which is rarely the case), Montgomery modular integer is preferred over plain modular integer (such as atcoder::modint).
For modulus with \(n\) bits, Montgomery reduction uses multiplication result of up to \(2n\) bits, whereas Barrett reduction (for modular multiplication of numbers stored in plain form) uses up to \(3n\) bits. Thus, for 32-bit modulus Barrett reduction is less SIMD-friendly due to requiring 128-bit multiplication, and for 64-bit modulus Barrett reduction is significantly slower due to requiring multi-precision multiplication.
When \(N<R/4\), where \(N\) is the modulus and \(R=2^{32}\) or \(2^{64}\) the Montgomery divisor, this implementation makes further optimization to reduce branching and improve SIMD-friendliness. We keep everything in \([0,2N)\) instead of \([0,N)\). The result of multiplication-Montgomery reduction of two numbers less than \(2N\), even without the final reduction step, is already less than \(((2N)(2N)+NR)/R=N(4N/R)+N<2N\), thus the final reduction step is not needed.
|
inlineexplicit |
Converts a plain integer to a Montgomery modular integer.
This constructor is marked explicit because the cost of conversion is non-trivial (requires one Montgomery reduction) and thus implicit conversion is discouraged.
|
inlineexplicit |
Converts a plain integer to a Montgomery modular integer.
This constructor is marked explicit because the cost of conversion is non-trivial (requires one Montgomery reduction) and thus implicit conversion is discouraged.
|
inline |
Returns the modular inverse.
Requires the underlying value to be invertible, i.e. coprime with the modulus.
|
inline |
Returns a number that is the same for the same residue class modulo the modulus.
This is faster than val(), but the number is not the remainder. Useful as key in associative containers.
|
inlinestatic |
Set the dynamic modint's modulus.
Calling this for static modint would be a compile error.
It maintains a stack of moduli. Push stack when it is called, and pop stack when the returned guard object is destructed. This allows recursively calling functions that use different moduli. However at any given moment you can only use one modulus.
| mod | Must be odd. |
|
related |
Type alias for 32-bit MontgomeryModInt with compile-time constant modulus.
| Mod | The modulus. Must be odd and less than \(2^{32}\). |
|
related |
Type alias for 64-bit MontgomeryModInt with compile-time constant modulus.
| Mod | The modulus. Must be odd and less than \(2^{64}\). |
|
related |
Given a modulus, calls a callable (visitor) with a dynamically selected fastest MontgomeryModInt type.
The visitor is called like visitor(mint(x)) where mint is the fastest dynamic MontgomeryModInt type that can handle mod as the modulus, and its modulus set to mod. The visitor should be able to accept different dynamic MontgomeryModInt types, similar to the visitor for std::visit.
1.9.6