Given a sequence of integers a1,?...,?an and q queries x1,?...,?xq on it. For each query xi you have to count the number of pairs (l,?r)such that 1?≤?l?≤?r?≤?n and gcd(al,?al?+?1,?...,?ar)?=?xi.
is a greatest common divisor of v1,?v2,?...,?vn, that is equal to a largest positive integer that divides all vi.
The first line of the input contains integer n, (1?≤?n?≤?105), denoting the length of the sequence. The next line contains n space separated integers a1,?...,?an, (1?≤?ai?≤?109).
The third line of the input contains integer q, (1?≤?q?≤?3?×?105), denoting the number of queries. Then follows q lines, each contain an integer xi, (1?≤?xi?≤?109).
For each query print the result in a separate line.
3 2 6 3 5 1 2 3 4 6
1 2 2 0 1
7 10 20 3 15 1000 60 16 10 1 2 3 4 5 6 10 20 60 1000
14 0 2 2 2 0 2 2 1 1
考数据结构的题，也是考数学功底的题，对于一段(l,r)从(l,l+1)开始的gcd严格单调递减，所以可用二分查出(l,r)里和(l,l)公约数一样的最大长度，之后又是新一轮的查找，因为一个数不会超过31个素因数，所以新一轮的查找不会很多，自己可以模拟一下，最多30次。具体做法就是枚举起点，终点始终是n，进行这种查找，找出来的数用map保存，最后的询问直接map回答。
这里还要求区间取GCD，线段树是不行的，因为此题卡了常数，所以得用ST算法，就算是ST，也得用位运算加速，即rmq的时候，不能用log，只能用31-__builtin_clz(v-s+1)，不然还是超时。。。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<string>
#include<cstring>
#include<algorithm>
#include<fstream>
#include<queue>
#include<stack>
#include<vector>
#include<cmath>
#include<iomanip>
#include<map>
#define rep(i,n) for(i=1;i<=n;i++)
#define MM(a,t) memset(a,t,sizeof(a))
#define INF 1e9
typedef long long ll;
#define mod 1000000007
using namespace std;
map<int,ll> mp;
int dp[100020][20],n,m;
int gcd(int a,int b){if(a==0) return b;if(b==0) return a;if(a<b) return gcd(b,a);if(a%b==0) return b;else return gcd(b,a%b);
}
void makermq(){int i,j;for(j=1;(1<<j)<=n;j++)for(i=1;i+(1<<j)-1<=n;i++)dp[i][j]=gcd(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
}
int rmq(int s,int v){int k=31-__builtin_clz(v-s+1);return gcd(dp[s][k],dp[v-(1<<k)+1][k]);
}
int main()
{int i,j;while(scanf("%d",&n)!=EOF){MM(dp,0);rep(i,n) scanf("%d",&dp[i][0]);makermq();mp.clear();rep(i,n){int st=i,l,r,tmp,mid,v;while(st<=n){v=st; l=st; r=n; tmp=rmq(i,l);while(l<=r){mid=(l+r)>>1;if(rmq(i,mid)==tmp){l=mid+1;v=mid; }else r=mid-1;} mp[tmp]+=v-st+1;st=v+1;} }scanf("%d",&m);while(m--){int tmp;scanf("%d",&tmp);printf("%I64d\n",mp[tmp]);}}return 0;
}