题意：
给定 $N$ 个数字， $Q$ 次询问，每次询问为查询下标在 $[l,r]$ 之间的所有数字中所有可能的子段的 $gcd$ 有多少种。$N,Q < 10^5 , a_i < 10^6$
题解：
首先一个重要的结论：以固定点为结尾的子段的 $gcd$ 种数不超过 $max(n,log(max(a_i)))$ 证明：每次往原有的序列里加入一个数字的话， $gcd$ 要么不变，要么至少变为原来的1/2，因此为指数级减小。
有了这个结论，我们可以试着来枚举一个端点考虑本题，不妨枚举每个段的右端点$r_j$ , 假设集合$S$表示以$r_{j-1}$ 为结尾的所有 $gcd$ ，那么要求出以$r_j$为结尾的所有 $gcd$ ，只需遍历S中的每个数字$d_k$，计算其与$a_j$ 的 $gcd$ ，放入新集合$S^{‘}$即可。这样的话我们可以得到一个空间为$O(nlogn)$的结果，表示以每个点为结尾的所有段的 $gcd$ 都是哪些数字。
现在来考虑查询。每次查询的话是要求出来$[l,r]$之间所有可能的 $gcd$ 。直接暴力不可取，由上面的结果可以试着考虑能否转化为前缀问题。可以发现，如果我们对所有的$[l,r]$离线处理，按$r$从小到大排序，并且按照这个顺序来调整已经遇到过的 $gcd$ 的信息的话，每次的查询只需要考虑有多少个 $gcd$ 出现的最右左端点大于等于l，这句话具体的意思是，一个 $gcd$ 可能出现过了很多次，不同的段都可以得到这个 $gcd$ ，但是我们只考虑这些段中左端点l_j最大的那个点$p_j$，这样的话如果$l<=p_j$那么可以确定$[l,r]$中一定有这个 $gcd$ （种类+1），这就就转化成了一个计数问题。 继续阅读“[离线处理][scheduling][数论结论][x] HDU5869 Different GCD Subarray Query”