鸡你太美
考虑求出 $r!$ 和 $(l-1)!$ 的唯一分解形式相除即可
by 向晚大魔王 @ 2022-11-25 16:22:40
可以做到 $\ O(len)$
by PosVII @ 2022-11-25 16:25:05
@[向晚大魔王](/user/427683) 求 $n!$ 的只因数分解和这个没有本质区别吧？
by NightTide @ 2022-11-25 16:25:27
@[PosVII](/user/271260) 怎么做？
by NightTide @ 2022-11-25 16:26:05
数据范围。
$n!$ 就是筛质数然后每个质数枚举幂统计吧。
by Sya_Resory @ 2022-11-25 16:29:03
@[Hoshino_kaede](/user/547908) srds，即使 $l=r$ 也至少需要 $O(\sqrt r)$ 级别罢，$O(len)$ 肯定做不到（）
转化为求 $n!$ 的只因数分解，先筛出所有质数，然后只需对每个质数 $p$，求 $\sum\limits_{i\geq1}\left\lfloor\dfrac{n}{p^i}\right\rfloor$ 即可。
by donghanwen1225 @ 2022-11-25 16:30:43
@[Sya_Resory](/user/114082) $l\le r \le 5\times 10^6$
by NightTide @ 2022-11-25 16:30:50
@[Hoshino_kaede](/user/547908) 思路和一楼相同，求出 $r!$ 和 $(l-1)!$ 的唯一分解形式，具体求法显然可以通过筛来搞。
如果我们想求 $x!$ 的唯一分解，显然在筛到 $i$ 的时候顺便可以找到它的最小只因子 $p$，然后可以转化为 $i = \frac{i}{p} \times p$ 的形式，记录下对于 $i$ 的每一个 $p$，然后设出现数组 $g$，初值全为 $1$。倒着枚举 $g$，然后 $g_{\frac{i}{p}} = g_{\frac{i}{p}} + g_i$，$f_p=f_p+g_i$。
by PosVII @ 2022-11-25 16:34:18
好像确实做不到 $O(len)$，只能做到 $O(n)$ /fad
by PosVII @ 2022-11-25 16:37:17
@[PosVII](/user/271260) $f$ 和 $g$ 分别是什么？
by NightTide @ 2022-11-25 16:37:58