2026 年江西预赛

思路

乘法阶必须在底数与模数互素时定义，且模素数 $q$ 的阶整除 $q-1$；$v_p(N)$ 表示 $p$ 在素因数分解中的指数。本题分别利用它们限制其他素因子大小和特殊因子重数。

想法从哪来：要求严格区间内最小整数，应先试下端点加1，若成功便无需搜索。 难点随即变成：这个候选的素因子会不会太小？先将特殊素因子 $p$ 用二项式展开分离，再对其余素因子 $q$ 研究 $(p-1{)}^p\equiv -1$。指数 $p$ 为素数让可能的乘法阶很少，一旦排除阶2，就迫使 $q$ 至少线性增长。 仍不必真的分解巨大的候选数。把每个素因子的权重 $e_q/q$ 与 $e_q\ln q$ 比较，再用 $\ln N=\sum e_q\ln q$ 合并。统一估计只处理大素数，小的 $p=3,5$ 直接检验。

若最接近下端点的整数 $N_0=(p-1{)}^p+1$ 已满足条件，它便自动是最小值。 关键是利用 $p$ 为奇素数：除 $p$ 外，$N_0$ 的每个素因子的乘法阶都是 $2p$， 因而这些素因子至少为 $2p+1$；再用对数把素因子指数总量统一估计。