警示后人:如果你TLE
查看原帖
警示后人:如果你TLE
588753
maxiaomeng楼主2025/8/1 15:14

注意到 p{10007,262203414,437367875}p\in \{10007,262203414,437367875\}

在 exLucas 算法中需要计算 n!modPQn! \bmod P^Q,其中一个步骤就是要计算 11PQP^Q 中不被 PP 整除的数的乘积对 PQP^Q 取模的值,记为 A(P,Q)A(P,Q)

由于 p{10007,262203414,437367875}p\in \{10007,262203414,437367875\}PQ{2,3,5,11,397,10007,53,73,1012}P^Q\in \{2,3,5,11,397,10007,5^3,7^3,101^2\}。我们可以对这些数预处理 A(P,Q)A(P,Q)。将原本 O(PQ)O(P^Q) 的计算优化到 O(1)O(1),效率显著提升。

实际上,经过计算,对于这些数,A(P,Q)1 (mod PQ)A(P,Q)\equiv -1\ (\bmod\ P^Q),因此连预处理都不用。

2025/8/1 15:14
加载中...