SP22549 DIVFACT4 - Divisors of factorial (extreme)

LuoGu: SP22549 DIVFACT4 - Divisors of factorial (extreme)

SPOJ: DIVFACT4 - Divisors of factorial (extreme)

对于一个质数 $p$ ，其指数为 $\sum _ k \lfloor \frac n {p ^ k} \rfloor$ 。考虑对于 $p \le \sqrt n$ ，可以暴力在 $\sqrt n \log \sqrt n$ 的时间内完成，可以接受。对于 $p > \sqrt n$ ，贡献只有 $\lfloor \frac n p \rfloor$ 。考虑数论分块，对于每个 $j = \lfloor \frac n i \rfloor$ ，我们需要计算出 $\sum _ {k = 2} ^ j [k \in Prime]$ 。可以用 Min_25 筛。

查看代码