LMCAS::ModInt类 参考

模整数类，封装模 p 下的算术运算 更多...

#include <modular_arithmetic.hpp>

LMCAS::ModInt 的协作图:

Public 成员函数
	ModInt ()
	默认构造，值为 0，模为 2
	ModInt (int64_t v, int64_t p)
	构造模整数
ModInt	inverse () const
	求模逆元
bool	is_zero () const
	判断是否为零
int64_t	modulus () const
	获取模数
bool	operator!= (const ModInt &other) const
	判不等
ModInt	operator* (const ModInt &other) const
	模乘法
ModInt	operator+ (const ModInt &other) const
	模加法
ModInt	operator- () const
	取负
ModInt	operator- (const ModInt &other) const
	模减法
ModInt	operator/ (const ModInt &other) const
	模除法（乘以逆元）
bool	operator< (const ModInt &other) const
	小于比较（先比模数，再比值）
bool	operator== (const ModInt &other) const
	判等
bool	operator> (const ModInt &other) const
	大于比较
int64_t	value () const
	获取当前值

静态 Public 成员函数
static ModInt	pow (ModInt base, int64_t exp)
	模幂运算

Private 成员函数
void	require_same_modulus (const ModInt &other) const

Private 属性
int64_t	mod_
int64_t	val_

详细描述

模整数类，封装模 p 下的算术运算

在文件 modular_arithmetic.hpp 第 126 行定义.

构造及析构函数说明

ModInt() [1/2]

LMCAS::ModInt::ModInt ( )

inline

默认构造，值为 0，模为 2

在文件 modular_arithmetic.hpp 第 138 行定义.

: val_(0), mod_(2) {}

引用了 mod_ , 以及 val_.

被这些函数引用 LMCAS::crt_checked(), inverse(), LMCAS::multi_crt(), LMCAS::multi_crt_checked(), operator!=(), operator*(), operator+(), operator-(), operator-(), operator/(), operator<(), operator==(), operator>(), pow() , 以及 require_same_modulus().

这是这个函数的调用关系图:

ModInt() [2/2]

LMCAS::ModInt::ModInt ( int64_t v, int64_t p )

inline

构造模整数

参数

v	整数值（自动取模归约到 [0, p)）
p	模数

在文件 modular_arithmetic.hpp 第 145 行定义.

                                 : mod_(p) {
        if (p <= 0) {
            throw std::domain_error("modulus must be positive");
        }
        val_ = v % p;
        if (val_ < 0) val_ += p;
    }

引用了 mod_, LMCAS::v , 以及 val_.

成员函数说明

inverse()

ModInt LMCAS::ModInt::inverse ( ) const

inline

求模逆元

返回

当前值在模 mod_ 下的乘法逆元

异常

std::domain_error

若值为 0 或不可逆

在文件 modular_arithmetic.hpp 第 224 行定义.

                           {
        if (val_ == 0) {
            throw std::domain_error("ModInt::inverse(): zero is not invertible");
        }
        int64_t s, t;
        int64_t g = extended_gcd(val_, mod_, s, t);
        if (g != 1) {
            throw std::domain_error(
                "ModInt::inverse(): element is not invertible (gcd != 1)");
        }
        return ModInt(s, mod_);
    }

引用了 ModInt(), LMCAS::extended_gcd(), mod_, LMCAS::t , 以及 val_.

被这些函数引用 operator/() , 以及 pow().

函数调用图:

这是这个函数的调用关系图:

is_zero()

bool LMCAS::ModInt::is_zero ( ) const

inline

判断是否为零

在文件 modular_arithmetic.hpp 第 217 行定义.

{ return val_ == 0; }

引用了 val_.

modulus()

int64_t LMCAS::ModInt::modulus ( ) const

inline

获取模数

在文件 modular_arithmetic.hpp 第 157 行定义.

{ return mod_; }

引用了 mod_.

operator!=()

bool LMCAS::ModInt::operator!= ( const ModInt & other ) const

inline

判不等

在文件 modular_arithmetic.hpp 第 201 行定义.

                                             {
        return !(*this == other);
    }

引用了 ModInt().

函数调用图:

operator*()

ModInt LMCAS::ModInt::operator* ( const ModInt & other ) const

inline

模乘法

在文件 modular_arithmetic.hpp 第 174 行定义.

                                                {
        require_same_modulus(other);
 
        uint64_t q;
        uint64_t result = lmmp_mulmod_ulong_(
            static_cast<uint64_t>(val_),
            static_cast<uint64_t>(other.val_),
            static_cast<uint64_t>(mod_), &q);
        return ModInt(static_cast<int64_t>(result), mod_);
    }

引用了 ModInt(), mod_, require_same_modulus() , 以及 val_.

函数调用图:

operator+()

ModInt LMCAS::ModInt::operator+ ( const ModInt & other ) const

inline

模加法

在文件 modular_arithmetic.hpp 第 160 行定义.

                                                {
        require_same_modulus(other);
        const int64_t distance = mod_ - other.val_;
        return ModInt(val_ >= distance ? val_ - distance : val_ + other.val_, mod_);
    }

引用了 ModInt(), mod_, require_same_modulus() , 以及 val_.

函数调用图:

operator-() [1/2]

ModInt LMCAS::ModInt::operator- ( ) const

inline

取负

在文件 modular_arithmetic.hpp 第 191 行定义.

                             {
        return ModInt(val_ == 0 ? 0 : mod_ - val_, mod_);
    }

引用了 ModInt(), mod_ , 以及 val_.

函数调用图:

operator-() [2/2]

ModInt LMCAS::ModInt::operator- ( const ModInt & other ) const

inline

模减法

在文件 modular_arithmetic.hpp 第 167 行定义.

                                                {
        require_same_modulus(other);
        return ModInt(val_ >= other.val_ ? val_ - other.val_
                                        : mod_ - (other.val_ - val_), mod_);
    }

引用了 ModInt(), mod_, require_same_modulus() , 以及 val_.

函数调用图:

operator/()

ModInt LMCAS::ModInt::operator/ ( const ModInt & other ) const

inline

模除法（乘以逆元）

在文件 modular_arithmetic.hpp 第 186 行定义.

                                                {
        return *this * other.inverse();
    }

引用了 ModInt() , 以及 inverse().

函数调用图:

operator<()

bool LMCAS::ModInt::operator< ( const ModInt & other ) const

inline

小于比较（先比模数，再比值）

在文件 modular_arithmetic.hpp 第 206 行定义.

                                              {
        if (mod_ != other.mod_) return mod_ < other.mod_;
        return val_ < other.val_;
    }

引用了 ModInt(), mod_ , 以及 val_.

函数调用图:

operator==()

bool LMCAS::ModInt::operator== ( const ModInt & other ) const

inline

判等

在文件 modular_arithmetic.hpp 第 196 行定义.

                                             {
        return val_ == other.val_ && mod_ == other.mod_;
    }

引用了 ModInt(), mod_ , 以及 val_.

函数调用图:

operator>()

bool LMCAS::ModInt::operator> ( const ModInt & other ) const

inline

大于比较

在文件 modular_arithmetic.hpp 第 212 行定义.

                                              {
        return other < *this;
    }

引用了 ModInt().

函数调用图:

pow()

ModInt LMCAS::ModInt::pow ( ModInt base, int64_t exp )

inlinestatic

模幂运算

参数

base	底数
exp	指数（可为负，负指数先求逆）

返回

base^exp mod p

在文件 modular_arithmetic.hpp 第 243 行定义.

                                                {
        uint64_t power = 0;
        if (exp < 0) {
            base = base.inverse();
            power = static_cast<uint64_t>(-(exp + 1)) + 1;
        } else {
            power = static_cast<uint64_t>(exp);
        }
        ModInt result(1, base.mod_);
        while (power != 0) {
            if ((power & 1U) != 0) result = result * base;
            power >>= 1U;
            if (power != 0) base = base * base;
        }
        return result;
    }

引用了 ModInt(), LMCAS::exp(), inverse() , 以及 mod_.

函数调用图:

require_same_modulus()

void LMCAS::ModInt::require_same_modulus ( const ModInt & other ) const

inlineprivate

在文件 modular_arithmetic.hpp 第 130 行定义.

                                                         {
        if (mod_ != other.mod_) {
            throw std::domain_error("modular operands must have the same modulus");
        }
    }

引用了 ModInt() , 以及 mod_.

被这些函数引用 operator*(), operator+() , 以及 operator-().

函数调用图:

这是这个函数的调用关系图:

value()

int64_t LMCAS::ModInt::value ( ) const

inline

获取当前值

在文件 modular_arithmetic.hpp 第 154 行定义.

{ return val_; }

引用了 val_.

类成员变量说明

mod_

int64_t LMCAS::ModInt::mod_

private

在文件 modular_arithmetic.hpp 第 128 行定义.

被这些函数引用 ModInt(), ModInt(), inverse(), modulus(), operator*(), operator+(), operator-(), operator-(), operator<(), operator==(), pow() , 以及 require_same_modulus().

val_

int64_t LMCAS::ModInt::val_

private

在文件 modular_arithmetic.hpp 第 127 行定义.

被这些函数引用 ModInt(), ModInt(), inverse(), is_zero(), operator*(), operator+(), operator-(), operator-(), operator<(), operator==() , 以及 value().

---

该类的文档由以下文件生成:

• include/modular_arithmetic.hpp