#define LMMP_API
Copyright (C) 2026 HJimmyK (Jericho Knox)
const mp_limb_t * mp_srcptr
void lmmp_divexact_unbalance_(mp_ptr dst, mp_srcptr np, mp_size_t nn, mp_srcptr dp, mp_size_t dn, mp_ptr dinv)
精确除法([dst,nn]=[np,nn]/[dp,dn],且余数必须为0)
mp_size_t lmmp_odd_nCr_uint_(mp_ptr dst, mp_size_t rn, uint n, uint r)
计算 nCr 组合数的奇数部分
mp_limb_t lmmp_cbrt_3_(mp_limb_t a0, mp_limb_t a1, mp_limb_t a2)
计算算数立方根 floor(cbrt(a0+a1*B+a2*B^2))
void lmmp_cbrt_6_fast_(mp_ptr dst, mp_ptr numa, mp_ptr tp)
计算算术立方根 [dst,2] = floor(cbrt([numa,6]))
void lmmp_sqrt_3_(mp_ptr dsts, mp_ptr dstr, mp_srcptr numa)
计算算术平方根 floor(sqrt([numa,3]))
uint lmmp_powmod_uint_odd_(uint base, ulong exp, uint mod)
计算 base^exp 对 mod 取模
mp_size_t lmmp_multinomial_size_(const uintp r, uint m, ulong *n)
计算多项式系数的 limb 缓冲区长度
ulong lmmp_prev_prime_ulong_(ulong n)
小于等于n的上一个素数
mp_size_t lmmp_odd_factorial_uint_(mp_ptr dst, mp_size_t rn, uint n)
计算 n!
void lmmp_sqrt_newton_(mp_ptr dsts, mp_srcptr numa, mp_size_t na, mp_size_t nf)
计算近似平方根 [dsts,nf+na/2+1]=[floor|round](sqrt([numa,na]*B^(2*nf)))
mp_size_t lmmp_nthroot_size_(mp_size_t na, ulong root)
计算 lmmp_nthroot_ 所需的 tp 缓冲区长度(任意长度输入入口)
mp_size_t lmmp_remove_(mp_ptr np, mp_size_t *nn, mp_srcptr dp, mp_size_t dn)
除去 [np,nn] 中的 [dp,dn] 的因子
void lmmp_powlo_(mp_ptr dst, mp_srcptr bp, mp_size_t n, mp_srcptr ep, mp_size_t en)
计算 [bp,n]^[ep,en] mod B^n,并将结果写入 [dst,n]
mp_size_t lmmp_gcd_lehmer_(mp_ptr dst, mp_srcptr up, mp_size_t un, mp_srcptr vp, mp_size_t vn)
计算两个无符号整数的最大公约数(Lehmer算法)
ulong lmmp_gcdext_11_(ulong u, ulong v, slong *s, slong *t)
扩展欧几里得(双 limb 标量):g = gcd(u,v),s*u + t*v = g
mp_size_t lmmp_fibonacci2_(mp_ptr dst, mp_ptr dst2, mp_size_t rn, ulong n)
计算 Fibonacci 数对:[dst,rn] = F[n],[dst2,rn] = F[n-1]
mp_size_t lmmp_u4_pow_1_(mp_ptr dst, mp_size_t rn, ulong base, ulong exp)
计算幂次方 [dst,rn] = [base,1] ^ exp
void lmmp_binvert_unbalance_1_(mp_ptr dst, mp_limb_t a, mp_size_t n)
计算 a 在 B^n 下的逆元
void lmmp_cbrt_newton_(mp_ptr dsts, mp_srcptr numa, mp_size_t na, mp_size_t nf)
计算近似立方根 [dsts,na/3+nf+1]=[floor|round](cbrt([numa,na]*B^(3*nf))), 输入须已归一化:na ≡ 0 (mod 3) 且顶 limb >= B...
mp_size_t lmmp_pow_1_size_(mp_limb_t base, ulong exp)
计算幂次方需要的limb缓冲区长度 base ^ exp
uint8_t uchar
Copyright (C) 2026 HJimmyK (Jericho Knox)
void lmmp_divexact_(mp_ptr dst, mp_srcptr np, mp_size_t nn, mp_srcptr dp, mp_size_t dn)
精确除法([dst,nn]=[np,nn]/[dp,dn],且余数必须为0)
ulong lmmp_modinv_ulong_(ulong u, ulong m)
模逆元(单 limb):求 u^{-1} mod m
mp_size_t lmmp_odd_nPr_ushort_(mp_ptr dst, mp_size_t rn, ulong n, ulong r)
计算 nPr 排列数的奇数部分
ulong lmmp_cbrt_chebyshev_(ulong n)
计算算数立方根 floor(cbrt(n))
void lmmp_sqrt_divide_(mp_ptr dst, mp_ptr numa, mp_size_t ns, mp_ptr tp, int calr)
计算算术平方根 floor(sqrt([numa,2*ns]))
mp_size_t lmmp_pow_win2_(mp_ptr dst, mp_size_t rn, mp_srcptr base, mp_size_t n, ulong exp)
计算幂次方2比特窗口快速幂算法 [dst,rn] = [base,n] ^ exp
bool lmmp_perfsqr_filter_1_(mp_limb_t p)
非完全平方数过滤器
mp_size_t lmmp_gcd_2_(mp_ptr dst, mp_srcptr up, mp_size_t un, mp_srcptr vp)
计算两个无符号整数的最大公约数
int lmmp_is_prime_2_notrial_(mp_limb_t lo, mp_limb_t hi)
判断 128 位素数(无试除法)
ulong lmmp_binvert_ulong_(ulong a)
计算 a 在2^64下的逆元
mp_size_t lmmp_arith_seqprod_size_(uint x, uint n, uint m)
计算等差数列乘积 x(x+m)...(x+n*m)的 limb 缓冲区长度
mp_limb_t lmmp_redc_(mp_ptr dst, mp_srcptr tp, mp_srcptr ninv, mp_srcptr mp, mp_size_t n)
Montgomery 归约(REDC):计算 ([tp,2n] + q*[mp,n]) / B^n,其中 q = [tp,n] * [ninv,n] mod B^n,即结果为 [tp,...
void lmmp_cbrt_(mp_ptr dsts, mp_ptr dstr, mp_srcptr numa, mp_size_t na, mp_size_t nf)
计算 [numa,na] * B^(3*nf) 的立方根和余数
void lmmp_powlo_2_(mp_ptr dst, mp_srcptr bp, mp_srcptr ep, mp_size_t en)
计算 [bp,2]^[ep,en] mod B^2,并将结果写入 [dst,2](lmmp_powlo_ 的 2 limb 特化)
void lmmp_binvert_n_dc_(mp_ptr dst, mp_srcptr numa, mp_size_t n, mp_ptr tp)
计算 [numa,n] 在 B^n 下的逆元
mp_size_t lmmp_u32_pow_1_(mp_ptr dst, mp_size_t rn, ulong base, ulong exp)
计算幂次方 [dst,rn] = [base,1] ^ exp
mp_size_t lmmp_pow_1_(mp_ptr dst, mp_size_t rn, mp_limb_t base, ulong exp)
计算幂次方 [dst,rn] = [base,1] ^ exp
void lmmp_powmod_1_(mp_ptr dst, mp_srcptr bp, mp_srcptr ep, mp_size_t en, mp_limb_t mod)
计算奇模数模幂 [dst,1] = [bp,1]^[ep,en] % mod
int lmmp_is_strong_lucas_(mp_srcptr np, mp_size_t nn)
强 Lucas-Selfridge 测试(大于 128 位)
ulong lmmp_cbrt_ulong_(ulong n)
计算算数立方根 floor(cbrt(n))
bool lmmp_is_prime_uint_(uint n)
判断素数
mp_size_t lmmp_superfac_size_(ushort n, mp_bitcnt_t *bits)
计算super阶乘的 limb 缓冲区长度
ulong lmmp_powmod_ulong_odd_(ulong base, ulong exp, ulong mod)
计算 base^exp 对 mod 取模
void lmmp_powmod_odd_(mp_ptr dst, mp_srcptr bp, mp_srcptr ep, mp_size_t en, mp_srcptr mp, mp_size_t n)
计算奇模数模幂 [dst,n] = [bp,n]^[ep,en] % [mp,n]
mp_size_t lmmp_2factorial_(mp_ptr dst, mp_bitcnt_t bits, mp_size_t rn, uint n)
计算 n!
uint lmmp_binvert_uint_(uint a)
计算 a 在2^32下的逆元
mp_size_t lmmp_pow_basecase_(mp_ptr dst, mp_size_t rn, mp_srcptr base, mp_size_t n, ulong exp)
计算奇数次幂算法 [dst,rn] = [base,n] ^ exp
void lmmp_powmod_(mp_ptr dst, mp_srcptr bp, mp_srcptr ep, mp_size_t en, mp_srcptr mp, mp_size_t n)
计算任意模数模幂 [dst,n] = [bp,n]^[ep,en] % [mp,n]
ulong lmmp_mulmod_ulong_(ulong a, ulong b, ulong mod, ulongp q)
计算两个无符号整数的乘积,对mod取模,商放入 q 中
int lmmp_is_prime_2_(mp_limb_t lo, mp_limb_t hi)
判断 128 位素数
void lmmp_divexact_basecase_(mp_ptr dst, mp_ptr np, mp_size_t nn, mp_srcptr dp, mp_size_t dn)
精确除法([dst,nn-dn+1]=[np,nn]/[dp,dn],且余数必须为0),朴素算法
mp_size_t lmmp_factorial_size_(uint n, mp_bitcnt_t *bits)
计算 n!
void lmmp_binvert_unbalance_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t n, mp_ptr tp)
计算 [numa,na] 在 B^n 下的逆元
mp_size_t lmmp_modinv_(mp_ptr dst, mp_srcptr up, mp_size_t un, mp_srcptr mp, mp_size_t mn)
模逆元(任意长度):求 [up,un]^{-1} mod [mp,mn]
mp_size_t lmmp_u64_pow_1_(mp_ptr dst, mp_size_t rn, ulong base, ulong exp)
计算幂次方 [dst,rn] = [base,1] ^ exp
mp_size_t lmmp_u8_pow_1_(mp_ptr dst, mp_size_t rn, ulong base, ulong exp)
计算幂次方 [dst,rn] = [base,1] ^ exp
void lmmp_binvert_2_(mp_ptr dst, mp_srcptr numa)
计算 [numa,2] 在 B^2 下的逆元
mp_size_t lmmp_hgcd_(lmmp_hgcd_matrix_t *M, mp_ptr ap, mp_ptr bp, mp_size_t n)
半扩展欧几里得:将数对原地归约至约一半规模,并累积变换矩阵
mp_size_t lmmp_primefac_size_(uint n)
计算质数阶乘的 limb 缓冲区长度
mp_size_t lmmp_hyperfac_(mp_ptr dst, mp_bitcnt_t bits, mp_size_t rn, ushort n)
计算hyper阶乘(k^k累乘至n)
mp_size_t lmmp_u16_pow_1_(mp_ptr dst, mp_size_t rn, ulong base, ulong exp)
计算幂次方 [dst,rn] = [base,1] ^ exp
mp_size_t lmmp_gcdext_(mp_ptr dstg, mp_ptr dsts, mp_ssize_t *sn, mp_ptr dstt, mp_ssize_t *tn, mp_srcptr up, mp_size_t un, mp_srcptr vp, mp_size_t vn)
扩展欧几里得(通用分发入口):g = gcd(u,v),s*u + t*v = g
void lmmp_binvert_3_(mp_ptr dst, mp_srcptr numa)
计算 [numa,3] 在 B^3 下的逆元
mp_size_t lmmp_gcdext_2_(mp_ptr dstg, mp_ptr dsts, mp_ssize_t *sn, mp_ptr dstt, mp_ssize_t *tn, mp_srcptr up, mp_size_t un, mp_srcptr vp)
扩展欧几里得(任意长度对双 limb):g = gcd([up,un],[vp,2]),s*u + t*v = g
mp_limb_t lmmp_sqrt_1_(mp_ptr dstr, mp_limb_t x)
计算算术平方根 floor(sqrt(x))
ulong lmmp_sqrt_ulong_(ulong a)
计算算术平方根 floor(sqrt(a))
void lmmp_divexact_1_(mp_ptr dst, mp_srcptr np, mp_size_t nn, mp_limb_t d, mp_limb_t dinv)
精确除法([dst,nn]=[np,nn]/d,且余数必须为0)
mp_limb_t lmmp_sqrt_2_(mp_ptr dstr, mp_srcptr numa)
计算算术平方根 floor(sqrt([numa,2]))
mp_size_t lmmp_2factorial_size_(uint n, mp_bitcnt_t *bits)
计算 n!
mp_size_t lmmp_factorial_(mp_ptr dst, mp_bitcnt_t bits, mp_size_t rn, uint n)
计算 n!
bool lmmp_perfsqr_(mp_srcptr p, mp_size_t n)
判断[p,n]是否为完全平方数
int lmmp_is_prime_n_notrial_(mp_srcptr np, mp_size_t nn, int strength)
大整数素性检验(无试除法,强度分档,大于 128 位)
mp_limb_t lmmp_gcd_11_(mp_limb_t u, mp_limb_t v)
计算两个无符号整数的最大公约数
mp_size_t lmmp_gcd_(mp_ptr dst, mp_srcptr up, mp_size_t un, mp_srcptr vp, mp_size_t vn)
计算两个无符号整数的最大公约数(通用分发入口)
mp_size_t lmmp_gcd_hgcd_(mp_ptr dst, mp_srcptr up, mp_size_t un, mp_srcptr vp, mp_size_t vn)
计算两个无符号整数的最大公约数(hgcd 分治,长输入优选)
mp_size_t lmmp_hyperfac_size_(ushort n, mp_bitcnt_t *bits)
计算hyper阶乘的 limb 缓冲区长度
mp_size_t lmmp_nCr_size_(uint n, uint r, mp_bitcnt_t *bits)
计算 nCr 组合数的 limb 缓冲区长度
void lmmp_binvert_4_(mp_ptr dst, mp_srcptr numa)
计算 [numa,4] 在 B^4 下的逆元
mp_size_t lmmp_nCr_(mp_ptr dst, mp_bitcnt_t bits, mp_size_t rn, uint n, uint r)
计算 nCr 组合数 ( nCr = n!
bool lmmp_is_prime_ulong_notrial_(ulong n)
判断素数(无试除法,单 limb 档)
mp_size_t lmmp_nPr_size_(ulong n, ulong r, mp_bitcnt_t *bits)
计算 nPr 排列数的 limb 缓冲区长度
mp_size_t lmmp_primefac_(mp_ptr dst, mp_size_t rn, uint n)
计算质数阶乘(不超过n的质数累乘)
mp_size_t lmmp_pow_(mp_ptr dst, mp_size_t rn, mp_srcptr base, mp_size_t n, ulong exp)
计算大整数幂 [dst,rn] = [base,n] ^ exp
void lmmp_sqrt_4_(mp_ptr dsts, mp_ptr dstr, mp_srcptr numa)
计算算术平方根 floor(sqrt([numa,4]))
int lmmp_is_prime_n_(mp_srcptr np, mp_size_t nn, int strength)
大整数素性检验(强度分档,大于 128 位)
void lmmp_divexact_2_(mp_ptr dst, mp_srcptr np, mp_size_t nn, mp_srcptr dp, mp_srcptr dinv)
精确除法([dst,nn]=[np,nn]/[dp,2],且余数必须为0)
void lmmp_cbrt_6_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
计算算术立方根 floor(cbrt([numa,na]))
bool lmmp_is_prime_ulong_(ulong n)
判断素数
ulong lmmp_nthroot_ulong_(ulong n, ulong root)
计算 floor(n^(1/root))
void lmmp_nthroot_(mp_ptr dsts, mp_ptr dstr, mp_srcptr numa, mp_size_t na, ulong root, mp_ptr tp)
计算算术根 [dsts,nr] = floor([numa,na]^(1/root))(任意 na/任意顶 limb)
mp_size_t lmmp_multinomial_(mp_ptr dst, mp_size_t rn, uint n, const uintp r, uint m)
计算多项式系数
void lmmp_hgcd_matrix_free_(lmmp_hgcd_matrix_t *M)
释放 hgcd 变换矩阵的元素缓冲
void lmmp_powmod_2_(mp_ptr dst, mp_srcptr bp, mp_srcptr ep, mp_size_t en, mp_srcptr mod)
计算奇模数模幂 [dst,2] = [bp,2]^[ep,en] % [mod,2]
mp_size_t lmmp_fibonacci_size_(ulong n)
计算 Fibonacci 数 F[n](及 F[n-1])所需的 limb 缓冲区长度
mp_size_t lmmp_fibonacci_(mp_ptr dst, mp_size_t rn, ulong n)
计算 Fibonacci 数 [dst,rn] = F[n]
mp_size_t lmmp_superfac_(mp_ptr dst, mp_bitcnt_t bits, mp_size_t rn, ushort n)
计算super阶乘(k!
int lmmp_is_prothprime_(uint k, mp_size_t n)
Proth 数 k*2^n+1 的素性判定(普罗斯定理)
void lmmp_invcbrt_newton_(mp_ptr dstis, mp_size_t ns, mp_srcptr numa, mp_size_t na)
计算逆立方根的定点下近似:记 I=floor(cbrt(B^(3*ns+na)/[numa,na])), 则 [dstis,ns+1] 满足 I-1 <= [dstis,...
mp_size_t lmmp_gcdext_1_(mp_ptr dstg, mp_ptr dsts, mp_ssize_t *sn, mp_ptr dstt, mp_ssize_t *tn, mp_srcptr up, mp_size_t un, ulong v)
扩展欧几里得(任意长度对单 limb):g = gcd([up,un],v),s*u + t*v = g
void lmmp_binvert_unbalance_2_(mp_ptr dst, mp_srcptr numa, mp_size_t n)
计算 [numa,2] 在 B^n 下的逆元
mp_size_t lmmp_gcdext_hgcd_(mp_ptr dstg, mp_ptr dsts, mp_ssize_t *sn, mp_ptr dstt, mp_ssize_t *tn, mp_srcptr up, mp_size_t un, mp_srcptr vp, mp_size_t vn)
扩展欧几里得(hgcd 分治,长输入优选):g = gcd(u,v),s*u + t*v = g
mp_size_t lmmp_gcdext_lehmer_(mp_ptr dstg, mp_ptr dsts, mp_ssize_t *sn, mp_ptr dstt, mp_ssize_t *tn, mp_srcptr up, mp_size_t un, mp_srcptr vp, mp_size_t vn)
扩展欧几里得(Lehmer 算法):g = gcd(u,v),s*u + t*v = g
mp_limb_t lmmp_mod_2p48sub1_(mp_srcptr p, mp_size_t n)
计算 [p,n] % 2^48-1
mp_size_t lmmp_arith_seqprod_(mp_ptr dst, mp_size_t rn, uint x, uint n, uint m)
计算等差数列乘积 x(x+m)...(x+n*m)
void lmmp_hgcd_matrix_init_(lmmp_hgcd_matrix_t *M, mp_size_t alloc)
初始化 hgcd 变换矩阵为单位矩阵(堆分配元素缓冲)
mp_limb_t lmmp_gcd_1_(mp_srcptr up, mp_size_t un, mp_limb_t v)
计算两个无符号整数的最大公约数
mp_size_t lmmp_pow_size_(mp_srcptr base, mp_size_t n, ulong exp)
计算幂次方需要的limb缓冲区长度 [base,n] ^ exp
mp_size_t lmmp_odd_nPr_ulong_(mp_ptr dst, mp_size_t rn, ulong n, ulong r)
计算 nPr 排列数的奇数部分
void lmmp_invsqrt_newton_(mp_ptr dstis, mp_size_t ns, mp_srcptr numa, mp_size_t na)
计算逆平方根的定点下近似:记 I=floor(sqrt(B^(2*ns+na)/[numa,na])), 则 [dstis,ns+1] 满足 I-1 <= [dstis,...
void lmmp_sqrt_(mp_ptr dsts, mp_ptr dstr, mp_srcptr numa, mp_size_t na, mp_size_t nf)
计算 [numa,na] * B^(2*nf) 的平方根和余数
mp_size_t lmmp_odd_nCr_ushort_(mp_ptr dst, mp_size_t rn, uint n, uint r)
计算 nCr 组合数的奇数部分
void lmmp_powlo_1_(mp_ptr dst, mp_srcptr bp, mp_srcptr ep, mp_size_t en)
计算 [bp,1]^[ep,en] mod B,并将结果写入 [dst,1](lmmp_powlo_ 的 1 limb 特化)
ulong lmmp_next_prime_ulong_(ulong n)
大于n的下一个素数
mp_size_t lmmp_nPr_(mp_ptr dst, mp_bitcnt_t bits, mp_size_t rn, ulong n, ulong r)
计算 nPr 排列数 ( nPr = n!
mp_size_t lmmp_gcd_22_(mp_ptr dst, mp_srcptr up, mp_srcptr vp)
计算两个无符号整数的最大公约数
mp_size_t lmmp_odd_nPr_uint_(mp_ptr dst, mp_size_t rn, ulong n, ulong r)
计算 nPr 排列数的奇数部分
void lmmp_cbrt_divide_(mp_ptr dst, mp_ptr numa, mp_size_t ns, mp_ptr tp, int calr)
计算算术立方根 floor(cbrt([numa,3*ns]))
bool lmmp_perfsqr_filter_(mp_srcptr p, mp_size_t n)
非完全平方数过滤器
void lmmp_binvert_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t n)
计算 [numa,na] 在 B^n 下的逆元
void lmmp_divexact_divide_(mp_ptr dst, mp_srcptr np, mp_size_t nn, mp_srcptr dp, mp_size_t dn)
精确除法([dst,nn]=[np,nn]/[dp,dn],且余数必须为0),分治算法