104 mp_size_t un = *u0n > *u1n ? *u0n : *u1n;
105 if (*u1n > *u0n && cy != 0) {
107 cy =
lmmp_add_1_(*u1p + *u0n, *u1p + *u0n, *u1n - *u0n, cy);
111 while (un > 1 && (*u1p)[un - 1] == 0)
139 if (un0 != 0 &&
M1->n[0][0] != 0) {
141 l0 = un0 +
M1->n[0][0];
143 if (un1 != 0 &&
M1->n[1][0] != 0) {
145 l1 = un1 +
M1->n[1][0];
148 if (l0 != 0 && l1 != 0) {
150 n0n = l1 > l0 ? l1 : l0;
153 }
else if (l0 != 0) {
159 while (n0n > 1 && u0p[n0n - 1] == 0)
164 if (un1 != 0 &&
M1->n[1][1] != 0) {
166 l2 = un1 +
M1->n[1][1];
168 if (un0 != 0 &&
M1->n[0][1] != 0) {
170 l3 = un0 +
M1->n[0][1];
173 if (l2 != 0 && l3 != 0) {
175 n1n = l2 > l3 ? l2 : l3;
178 }
else if (l2 != 0) {
184 while (n1n > 1 && u1p[n1n - 1] == 0)
207 cmp2 = twon < u0n ? -1 : 1;
213 *sneg = cmp2 == 0 ? 0 : det < 0;
219 while (rn > 0 && sp[rn - 1] == 0)
221 *sneg = (det > 0 && rn != 0);
239 while (pn > 0 && nb[pn - 1] == 0)
251 while (pn > 0 && nb[pn - 1] == 0)
275 while (nn > 0 && np[nn - 1] == 0)
282 while (yn2 > 0 && yt[yn2 - 1] == 0)
296 while (rn > 0 && qt[rn - 1] == 0)
311 mp_size_t rn =
lmmp_gcdext_derive_(dstt, &tneg, gp, gn, sp, sun, suneg, up, un, vp, vn,
325 mp_size_t rn =
lmmp_gcdext_derive_(dsts, &tneg, gp, gn, sp, sun, suneg, up, un, vp, vn, nb,
348 lmmp_param_assert(up != NULL && vp != NULL && dstg != NULL && dsts != NULL && sn != NULL);
357 }
else if (un == vn) {
389 mp_ptr wb = wbuf + (n0 + 1);
390 mp_ptr sa = wbuf + 2 * (n0 + 1);
391 mp_ptr sb = wbuf + 3 * (n0 + 1);
392 mp_ptr mbuf1 = wbuf + 4 * (n0 + 1);
393 mp_ptr u0p = mbuf1 + 4 * mcap;
394 mp_ptr u1p = u0p + (n0 + 2);
395 mp_ptr scbuf = u1p + (n0 + 2);
397 mp_ptr nb = sp + (n0 + 2);
398 mp_ptr yt = nb + (2 * n0 + 4);
399 mp_ptr p1b = yt + (2 * n0 + 4);
400 mp_ptr p2b = p1b + (2 * n0 + 8);
465 int degenerate = (2 * nb_cur <=
n);
479 mp_size_t rn =
lmmp_hgcd_adjust_(&
M1, dsub, sa, sb, &blen, wa + p, wb + p, nn, wa, wb,
483 if (rn > 0 && rn < n && blen > maxlen) {
494 int rr = rowz ? 0 : 1;
499 det = rowz ? -dsub : dsub;
520 if (r1n < nb_cur || (r1n == nb_cur &&
lmmp_cmp_(sa, wb, r1n) < 0)) {
542 mp_size_t qn =
n - nb_cur + 1 - (q[
n - nb_cur] == 0);
544 if (qn == 1 && q[0] < (1ull << 63)) {
547 }
else if (u0n == 0) {
556 while (pn > 0 && t1[pn - 1] == 0)
566 r0n = pn > u1n ? pn : u1n;
601 lmmp_gcdext_emit_(dstg, dsts, sn, dstt, tn, wa, gn, sp, sun, suneg, sw, up, un, vp, vn, nb,
616 if (snabs != 0 && u1n != 0) {
619 while (p1n > 0 && p1b[p1n - 1] == 0)
622 if (tnabs != 0 && u0n != 0) {
625 while (p2n > 0 && p2b[p2n - 1] == 0)
630 if (det < 0 && sun != 0)
643 while (pn > 0 && p1b[pn - 1] == 0)
647 int cmp2 = (twon != vn) ? (twon < vn ? -1 : 1) :
lmmp_cmp_(p2b, vp, vn);
652 while (dnn > 0 && db[dnn - 1] == 0)
657 int cmp2s = (twosn != dnn) ? (twosn < dnn ? -1 : 1) :
lmmp_cmp_(p2b, db, dnn);
664 int cD = (sun != dnn) ? (sun < dnn ? -1 : 1) :
lmmp_cmp_(sp, db, dnn);
667 while (sun > 0 && sp[sun - 1] == 0)
672 while (sun > 0 && sp[sun - 1] == 0)
681 }
else if (cmp2 == 0) {
685 lmmp_gcdext_emit_(dstg, dsts, sn, dstt, tn, gb, gn, sp, sun, suneg, sw, up, un, vp, vn, nb,
695 lmmp_param_assert(up != NULL && vp != NULL && dstg != NULL && dsts != NULL && sn != NULL);
700 if (vn == 2 && un > 2)
721 return s < 0 ? m - sm : sm;
754 while (rn > 0 && r[rn - 1] == 0)
762 if (gn != 1 || g[0] != 1) {
777 while (snn > 0 &&
s[snn - 1] == 0)
mp_size_t lmmp_hgcd_scratch_size_(mp_size_t n)
计算 hgcd 内部临时空间大小(容量上界推导见 hgcd.c 定义处注)
static void lmmp_gcdext_smag_(mp_ptr dst, mp_size_t *n, int *neg, mp_srcptr x, mp_size_t xn, int xneg, mp_srcptr y, mp_size_t yn, int yneg)
mp_size_t lmmp_hgcd_core_(lmmp_hgcd_matrix_t *M, mp_ptr ap, mp_ptr bp, mp_size_t n, lmmp_hgcd_scratch_t *sc, int *detsign, int appr)
hgcd 递归核:将数对归约至约 n/2 规模并累积变换矩阵(详见 hgcd.c 实现注)
static mp_size_t lmmp_gcd_norm_(mp_srcptr p, mp_size_t n)
mp_size_t lmmp_hgcd_adjust_(lmmp_hgcd_matrix_t *M1, int detsign, mp_ptr dap, mp_ptr dbp, mp_size_t *blen, mp_srcptr ha, mp_srcptr hb, mp_size_t hn0, mp_srcptr ap, mp_srcptr bp, mp_size_t n, mp_size_t p, lmmp_hgcd_scratch_t *sc)
高位直写 + 低位修补:将子递归成果(矩阵 M1 与归约后的高位对)合入完整数对
mp_size_t lmmp_gcdext_derive_(mp_ptr dst, int *tneg, mp_srcptr gp, mp_size_t gn, mp_srcptr sp, mp_size_t sn, int sneg, mp_srcptr xp, mp_size_t xn, mp_srcptr yp, mp_size_t yn, mp_ptr nb, mp_ptr yt, mp_ptr qt)
导出另一侧系数:tv = (g - S·X)/Y(S 为 X 侧系数,恒等式保证整除)
#define HGCD_RECURSE_THRESHOLD
Copyright (C) 2026 HJimmyK (Jericho Knox)
static mp_ptr lmmp_hgcd_salloc_(lmmp_hgcd_scratch_t *sc, mp_size_t n)
static mp_size_t lmmp_gcd_matrix_maxlen_(const lmmp_hgcd_matrix_t *M)
static void lmmp_gcd_mul_(mp_ptr dst, mp_srcptr a, mp_size_t an, mp_srcptr b, mp_size_t bn)
void lmmp_gcdext_emit_(mp_ptr dstg, mp_ptr dsts, mp_ssize_t *sn, mp_ptr dstt, mp_ssize_t *tn, mp_srcptr gp, mp_size_t gn, mp_srcptr sp, mp_size_t sun, int suneg, int sw, mp_srcptr up, mp_size_t un, mp_srcptr vp, mp_size_t vn, mp_ptr nb, mp_ptr yt, mp_ptr qt)
发射:g 与 S(值序大者系数)按 sw 映射到 (dsts,dstt),另一系数经恒等式导出
static void lmmp_gcd_matrix_init_buf_(lmmp_hgcd_matrix_t *M, mp_ptr buf, mp_size_t alloc)
static void lmmp_gcd_matrix_swap_cols_(lmmp_hgcd_matrix_t *M)
static mp_size_t gcdext_pick_s_(mp_ptr sp, int *sneg, mp_srcptr u0p, mp_size_t u0n, mp_srcptr u1p, mp_size_t u1n, int det, mp_ptr t1)
static void gcdext_row_qscalar_(mp_ptr *u0p, mp_ptr *u1p, mp_size_t *u0n, mp_size_t *u1n, ulong q)
Copyright (C) 2026 HJimmyK (Jericho Knox)
static void gcdext_row_mul_(mp_ptr u0p, mp_ptr u1p, mp_size_t *u0n, mp_size_t *u1n, const lmmp_hgcd_matrix_t *M1, lmmp_hgcd_scratch_t *sc)
#define LMMP_SWAP(x, y, type)
交换两个变量的值
#define lmmp_copy(dst, src, n)
#define lmmp_zero(dst, n)
#define lmmp_debug_assert(x)
const mp_limb_t * mp_srcptr
void lmmp_free(void *ptr)
内存释放函数(调用lmmp_heap_free_fn)
#define LMMP_VECT_CONSERVATIVE
#define lmmp_param_assert(x)
static mp_limb_t lmmp_add_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
加法静态内联函数 [dst,na]=[numa,na]+[numb,nb]
static mp_limb_t lmmp_add_1_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_limb_t x)
加单精度数静态内联函数 [dst,na]=[numa,na]+x
mp_limb_t lmmp_shr_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t shr)
右移操作 [dst,na] = [numa,na]>>shr,dst的高shr位填充0
mp_limb_t lmmp_mod_1_(mp_srcptr numa, mp_size_t na, mp_limb_t x)
单精度数取余
void lmmp_mul_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
不等长乘法操作 [dst,na+nb] = [numa,na] * [numb,nb]
int lmmp_cmp_(mp_srcptr numa, mp_srcptr numb, mp_size_t n)
比较函数
static mp_limb_t lmmp_sub_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
减法静态内联函数 [dst,na]=[numa,na]-[numb,nb]
mp_limb_t lmmp_addmul_1_(mp_ptr numa, mp_srcptr numb, mp_size_t n, mp_limb_t b)
乘以单limb并累加操作 [numa,n] += [numb,n] * b
mp_limb_t lmmp_mul_1_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_limb_t x)
乘以单limb操作 [dst,na] = [numa,na] * x
void lmmp_div_(mp_ptr dstq, mp_ptr dstr, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
除法和取模操作
#define ctz_shr_u64(r, x, cnt)
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define GCD_HGCD_THRESHOLD
ulong lmmp_gcdext_11_(ulong u, ulong v, slong *s, slong *t)
扩展欧几里得(双 limb 标量):g = gcd(u,v),s*u + t*v = g
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_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_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
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_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
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
#define ALLOC_TYPE(n, type)
#define BALLOC_TYPE(n, type)