长度为N的正整数序列S，有Q次询问，每次询问一段区间内所有数的lcm(即最小公倍数)。由于答案可能很大，输出答案Mod 10^9 + 7。
感觉非常好的一道题目
gyz的题解也写得非常详细了
首先，对于一个数x，它的素因子的个数是O(logx)级别的，每一个素因子的幂次也是O(logx)级别的
要求[l,r]的lcm，也就是说对于[l,r]出现的每一个素数p，我们要知道p的最大的幂次。
但是直接维护这个是很麻烦的，我们转而从贡献的角度看。
比如一个数x有p^q，我们把这个看成p^1,p^2,...,p^q这q个不相关的数，每一个数对答案的贡献都是p，那么如果这个区间里p的最大幂次是q的话，那么转化成这个区间有p^1,p^2,...,p^q这q个数，每一个数的贡献为p，那么总贡献就是p^q,等价于原来的贡献。
把每一个数的每一个素因子表示成pair的形式，(pre_pos[p^1],p),(pre_pos[p^2],p),...,(pre_pos[p^q],p)
则现在问题变成了对于一个区间[l,r]，这个区间的数的级别是O((r-l+1)log^2x)的，即有这么多的pair，我们要求的是这些pair(x,y)中，满足x < l的所有pair的y的积。
为什么这里是x < l呢？
这是一个很经典的套路了，记录一个数x的上一个出现的位置，那么这个数在[l,r]中没有重复的条件是
pre_pos[x] < l。
在线求的话，可以用主席树，但是我觉得空间可能会爆，就没有写了。
离线的话？
我们把询问[l,r]满足x < l转化为询问[1,r] - 询问[1,l - 1]，这样可以用树状数组维护前缀积了。
具体的说，
我们把每一个询问拆分成[1,l - 1]和[1,r]
每一询问是有2个信息的(r,x)，表示我们把数组r之前的所有数形成的pair加入bit中后，就可以询问了，询问的区间是[1,x]
所以[l,r]实际上是拆成了(l,l - 1)和(r,l - 1)
然后按询问(r,x)的r排序询问，然后每次询问r，我们都把数组位置<=r的数构成的pair加入到树状数组中，然后这个时候询问的区间不是[1,r]而是[1,x]
其实排序后依次处理询问，然后每次询问我们确保需要的信息放到数据结构里面，这个套路也是很常见了。
[l,r]变为[1,r] - [1,l - 1]这个套路也很常见。
主要p^q这个数有p^q的贡献，把这个转化成有p^1,p^2,...,p^q这q个数，每一个数的贡献都是p，然后这q个数可以相互独立来维护，这个转化很厉害阿？