题解 | #数学家的迷题#
数学家的迷题
https://ac.nowcoder.com/acm/contest/11175/D
数学家的迷题
对于操作2，其答案为区间内元素不同质因数的个数。
注意到，而
内的素数个数约有
个。如果使用
bitset存储每个元素的质因数，再用线段树维护区间内bitset或和，即可求得区间内元素不同质因数，进一步就可以获取其质因数个数。
对于一个数，可以
求出其所有质因数，所以建线段树的复杂度为
，单点更新的复杂度为
，区间询问的复杂度为
。
优化
其实上面的做法已经足够AC了，但是还有可以优化的地方。就是对于而言，大于
的质因数至多有1个，所以可以用一个更小的
bitset，配合一个维护大于的质因数的
set来保存的所有质因数。
投递中国电科等公司10个岗位 >