https://vjudge.net/problem/47450/origin

题意：

有一个含有n个数的序列，m个询问。问 [l, r] 区间内与所有数都互质的数有几个？

思路：

想到了预处理每个数最左最右的，最远的互质的数的范围。。

之后对于询问区间[l,r]，我们要知道 对于 i>=L && i <= R 并且 a[i].l<=L，a[i].r>=R的i的个数...

没有想到怎么维护,gg

转载一段题解：

先算出每个数的有效范围，l[i]，r[i]代表与第i个数一直互质到的最左端和最右端。这个处理方法是，预处理出一张因子表。然后对每个输入的数，判断其因子出现的最接近它的位置。从左到右扫一遍求出l[i]，从右到左扫一遍求出r[i]；我们还需要用一个vector记录下左边界为i时的所有数。

我们思考一个范围内，当一个数的l[i]和r[i]都在范围之外时，这个数会被统计在内。反过来讲就是一个范围在一个数的边界之内，当前的数会被统计到范围之内。

我们先对问题进行离线处理，先根据问题的左边界排序。我们需要维护一个树状数组来统计和增减值。

然后我们按照i从1到n扫一遍，i代表的意义是左边界。

1. 当扫到第i个数时，我们统计左边界为i+1的问题(这样范围一定满足左边界，因为右边界接下来也进行了处理，所以可以直接统计）。

2.  我们还需要更新第i个数。i的意义是左边界，因为之后统计的问题左边界都大于i，都满足。所以我们找到所有左边界为i的数，将其+1处理。然后右边界-1处理。这样如果问题的边界大于右边界的话，这个数就不会统计在内。

3.  最后处理完i后，因为以后问题的左边界都大于i，所以第i个数不会再被统计了，所以我们要除去第i个数的影响，就是把其右边界+1（自身为什么不处理，因为处不处理都一样，不会在涉及到它本身了）

转载又一段题解：

先预处理出来每个数的贡献区间，每个数的贡献区间是 [左边最近不互质数的位置，右边最近不互质数的位置] ，现在问题就转化为了求区间 [L, R] 中有几个数的贡献区间能完整覆盖 [L, R] 区间。但是数据范围挺大的，可以考虑用树状数组离线处理来达到优化的目的。先对所有的查询进行排序 (按照L升序排列) ，然后从左到右依次处理。我们用树状数组区间和sum [L, R] 表示区间[L, R]中符合题意的有多少个数。假设现在需要查询 [L, R] 区间，我们可以考虑贡献区间L[i]