HDU - 5869 Different GCD Subarray Query 树状数组离线处理
传送门:HDU5869题意:给出一个长度为n的序列和m次询问,每次询问给出l,r,求[l, r]区间内所有子序列不同gcd的个数。思路:首先明确对于一个序列a[l...r]的所有以a[l]开头的子序列,所能得到的不同gcd的个数最多有log(a[l])个。那么这个题中我们就可以对于每一个位置,预处理出以该位置为结尾的所有不同gcd的最大左边界(即L至少要到这个位置才能在L~R这个区间中能形