感觉就很生草。  提供两种解法，分别是线段树套 bitset 的 和 。  考场上开场开了 D ，第一反应就是分块套 bitset ，算了算时间复杂度肯定爆了，就弃掉了，旁边的同学打了后直接 T 掉。  想了一会儿想到了以前做 Ynoi 时写过一道线段树套线性基的题，就随口说了句是不是可以线段树套 bitset 啊，同学听了后觉得很妙于是一打就过了……  其实就是对于每个数维护一下它包含了哪些质因子，在 以内质数个数数量级在 左右，所以我们考虑用一个长为 的 bitset 来记录每个质因子是否出现，因为信息的合并性比较弱所以可以不分块，用线段树维护一个区间的 bitset 即可。  修改时单点...