exLucas 平替

我们知道，exLucas 是 $\mathcal O(\min(n,p))$ 的，所以 $p$ 很小时， $n$ 可以开到 $10^{18}$ 。

不过很多时候，只是模数为合数而已，远没到 $n$ 很大的地步，这个时候我们无需耗费精力学习 exLucas，可以直接使用它的平替。

预处理 $\mathcal O(\sqrt p+n\omega(p))$ ，询问 $\mathcal O(\omega(p))$ 。

看到复杂度想必您已经会了，将 $p$ 质因数分解，对于非 $p$ 质因子的质数，它们存在逆元，我们可以照常处理阶乘、阶乘逆元中不含 $p$ 质因数的部分。

值得注意的是，对一个质数 $x$ ，将 $[1,n]$ 中的所有数去除掉 $x$ 这个因子，暴力除的复杂度是 $\mathcal O(n)$ 的，以密度最高的 $2$ 为例分析就可以利用等比数列求和算出这个结果。

而对于 $p$ 的因子部分，我们可以预处理 $\omega(p)$ 个数组表示每个因子在阶乘中的次数，而后 $\frac{n!}{m!(n-m)!}$ 中 $x$ 的次数只需 $s_n-s_m-s_{n-m}$ 来算出，再预处理幂次即可算出这部分贡献。

如果空间告急，我们还有另一种计算方法 $cnt(n!,p)=\sum_{c\ge 1}\lfloor\frac n {p^c}\rfloor$ ，然后配合快速幂也可以实现询问多一个 $\log p$ ，空间少一个 $\omega(p)$ 。