通过这道题目还是学到了不少东西的，当时刚拿到这个题目的时候时间已经不多了，因为前面有个C坑到了，看了个大概，然后就往线段树和树状数组方面去想了，对于gcd的区间求一个前缀，再搞一个后缀 瞎弄弄，后来发现错了，题目求的是区间个数。。。又浪费了一段时间，然后回头再看看，大致就想到了暴力枚举，n是10^5，大不了离线先暴力的高出答案，想到一般发现 若假定一个询问输入的数 为 X,那么另一个 能够 y 通过gcd(x,y)得到的另一个数的 答案就是它自身的答案数再加上当前x的答案数，这样就有递推了，于是赶紧写了一下，结果T了！，没有做出来，补题也拖了很久。。。后来发现 自己的错误之处，其实对于G(l,r),G(l,r+1)后者肯定比前者更小，这句话在一个博客中也看到了，自己当时 顺序没写好。。。后来看到一个博客推荐的另一个 博客，发现了一个很好的解决办法
是以POJ3368为例子，然后看的半懂不懂的 ，磕磕碰碰的去把POJ3368给A了，又做了这道题目也过了，后来看CF的官方，题解发现了另一种解法，
这篇博客就是第二种解法
枚举的是区间，然后利用两个map 类似于滚动数组一样进行传递再利用，保存在另一个map里，，这个方法最好理解也非常简洁，参照他的 敲了一发 ，顺便纪念一下！
map<int ,ll> res;map<int ,int >now,nex;map<int ,int > ::iterator it;int n;int aa[100000 + 55];int q;void init() {memset(aa,0,sizeof(aa));}bool input() {while(cin>>n) {for(int i=0;i<n;i++)scanf("%d",&aa[i]);return false;}return true;}int Gcd(int a,int b) {return b == 0?a:Gcd(b,a%b);}void cal() {for(int i=0;i<n;i++) {nex.clear();for(it=now.begin();it!=now.end();it++)nex[Gcd(it->first,aa[i])] += it->second;nex[aa[i]]++;swap(nex,now);for(it = now.begin();it != now.end();it++)res[it->first] += it->second;}int q;cin>>q;while(q–) {int x;scanf("%d",&x);printf("%I64d\n",res[x]);}}void output() {}int main() {while(true) {init();if(input())return 0;cal();output();}return 0;}
人的价值，在遭受诱-惑的一瞬间被决定
