数学家的迷题

对于操作2，其答案为区间内元素不同质因数的个数。

注意到，而内的素数个数约有个。如果使用bitset存储每个元素的质因数，再用线段树维护区间内bitset或和，即可求得区间内元素不同质因数，进一步就可以获取其质因数个数。

对于一个数，可以求出其所有质因数，所以建线段树的复杂度为，单点更新的复杂度为，区间询问的复杂度为。

优化

其实上面的做法已经足够AC了，但是还有可以优化的地方。就是对于而言，大于的质因数至多有1个，所以可以用一个更小的bitset，配合一个维护大于的质因数的set来保存的所有质因数。