Blog of RuSun

OneProblemIsDifficultBecauseYouDontKnowWhyItIsDiffucult

SP22549 DIVFACT4 - Divisors of factorial (extreme)

LuoGu: SP22549 DIVFACT4 - Divisors of factorial (extreme)

SPOJ: DIVFACT4 - Divisors of factorial (extreme)

对于一个质数 p ,其指数为 knpk 。考虑对于 pn ,可以暴力在 nlogn 的时间内完成,可以接受。对于 p>n ,贡献只有 np 。考虑数论分块,对于每个 j=ni ,我们需要计算出 k=2j[kPrime] 。可以用 Min_25 筛。

查看代码
1

Gitalk 加载中 ...