JZOJ 4620. 【NOI2016模拟7.13】Jason做奥数

题目

解题思路

首先，这道题目有一个关键的信息：要求的是各lcm的积。
这说明了什么？每个pc$p^c$可以一一处理！
考虑lcm$lcm$中，质数p$p$的指数为c$c$出现了多少次？
那么答案就是：
Πp∈质数,pc≤L    pc对应的次数${\mathrm{\Pi }}_{p\in 质数,p^c\le L}{p}^{c^{对应的次数}}$
这好像挺难算的。那么考虑容斥，将对应的次数为Ans(≤pc+1)−Ans(≤pc)$Ans(\le p^{c+1})-Ans(\le p^c)$。
显然，就是(L−⌊Lpc+1⌋)n−(L−⌊Lpc⌋)n$(L-\lfloor \frac{L}{p^{c+1}}\rfloor {)}^n-(L-\lfloor \frac{L}{p^c}\rfloor {)}^n$。
但是，这样子暴力枚举会超时！！！
考虑分块。
若p＞n−−√$p＞\sqrt{n}$，则说明⌊Lpc+1⌋=0$\lfloor \frac{L}{p^{c+1}}\rfloor =0$，对应的次数只有Ln−(L−⌊Lp⌋)n$L^n-(L-\lfloor \frac{L}{p}\rfloor {)}^n$，会有多个⌊Lp⌋$\lfloor \frac{L}{p}\rfloor$相同。
这题最关键的是容斥，还有P$P$是质数，这样可以爽快地用欧拉定理。