modular_arithmetic.hpp 文件参考

模运算工具：ModInt 类、扩展欧几里得、CRT、有理重构。 更多...

#include <cstdint>
#include <vector>
#include <utility>
#include <cmath>
#include <stdexcept>
#include <algorithm>
#include <limits>
#include <string>
#include "computation_context.hpp"
#include <lmmp.h>
#include <numth.h>
#include "result.hpp"

modular_arithmetic.hpp 的引用(Include)关系图:

此图展示该文件被哪些文件直接或间接地引用了:

浏览该文件的源代码.

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

命名空间
namespace	LMCAS
namespace	LMCAS::modular_detail

类型定义
using	LMCAS::CrtResult = Result<std::pair<int64_t, int64_t>>
using	LMCAS::RationalReconstructionResult = Result<std::pair<int64_t, int64_t>>

函数
uint64_t	LMCAS::modular_detail::abs_to_u64 (int64_t value)
bool	LMCAS::modular_detail::checked_positive_product (int64_t a, int64_t b, int64_t &out)
std::pair< int64_t, int64_t >	LMCAS::crt (int64_t r1, int64_t m1, int64_t r2, int64_t m2)
	中国剩余定理（两模数），返回规范余数与模数乘积。
CrtResult	LMCAS::crt_checked (int64_t r1, int64_t m1, int64_t r2, int64_t m2)
CrtResult	LMCAS::crt_checked (int64_t r1, int64_t m1, int64_t r2, int64_t m2, ComputationContext &context)
	Checked Chinese remainder theorem for two positive coprime moduli.
int64_t	LMCAS::extended_gcd (int64_t a, int64_t b, int64_t &s, int64_t &t)
	用扩展欧几里得算法求 gcd(a,b) 及 Bezout 系数。
std::vector< int64_t >	LMCAS::generate_good_primes (int count, const std::vector< BigInt > &leading_coeffs, uint64_t start_from=UINT64_C(1000000000))
	生成指定数量的好素数
bool	LMCAS::is_good_prime (int64_t p, const std::vector< BigInt > &leading_coeffs)
	判断素数 p 是否为"好素数"（不整除任何首项系数）
uint64_t	LMCAS::lammp_gcd (uint64_t a, uint64_t b)
	计算两个无符号整数的最大公约数（调用 LMMP）
bool	LMCAS::lammp_is_prime (uint64_t n)
	判断无符号整数是否为素数
uint64_t	LMCAS::lammp_next_prime (uint64_t n)
	求大于 n 的下一个素数
std::pair< int64_t, int64_t >	LMCAS::multi_crt (const std::vector< int64_t > &residues, const std::vector< int64_t > &primes)
	多模数中国剩余定理
CrtResult	LMCAS::multi_crt_checked (const std::vector< int64_t > &residues, const std::vector< int64_t > &primes)
CrtResult	LMCAS::multi_crt_checked (const std::vector< int64_t > &residues, const std::vector< int64_t > &primes, ComputationContext &context)
	Checked CRT for a non-empty list of pairwise coprime positive moduli.
RationalReconstructionResult	LMCAS::rational_reconstruction_checked (int64_t x, int64_t m)
RationalReconstructionResult	LMCAS::rational_reconstruction_checked (int64_t x, int64_t m, ComputationContext &context)
	Checked rational reconstruction.

变量
constexpr int64_t	LMCAS::MODULAR_PRIMES []
	预定义的大素数表，用于模运算多素数方案
constexpr size_t	LMCAS::NUM_MODULAR_PRIMES = sizeof(MODULAR_PRIMES) / sizeof(MODULAR_PRIMES[0])
	预定义素数表的长度

详细描述

模运算工具：ModInt 类、扩展欧几里得、CRT、有理重构。

在文件 modular_arithmetic.hpp 中定义.