题目描述

小美拿到了一个数组，她有$q$次查询，每次询问一个区间内所有元素的乘积有多少因子。你能帮帮她吗?

注:由于数组元素过多，所以是按连续段的方式给定。例如，[1,1,2,3,3,3]有2个1，1个2，3个3，因此表示为<2,1>,<1,2>,<3,3>。

思路

二分 + 前缀和。

一个数的因子数等于其 每个质因子 $p_i$ 的数量加1 的乘积，即 $\prod\limits_{i} (cnt_{p_i}+1)$

$q$ 次询问，要求我们单次查询需要控制在 $O(\log n)$ 内。

因为 $10$ 以内只有 $2,3,5,7$ 这 4 个质数，所以可以对这 4 个质数预处理前缀和