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 筛。

查看代码