这道题很妙啊。其实我们可以发现重要的不是起点和终点，重要的是个数，然后脑洞一下，可以递推。（我什么都没有想出来）假设我们已经知道了前面所有子串的gcd，那么我们可以用现在的a[i]和前面每个数求gcd，这样就把加入这个新元素的串的所有情况都枚举了一遍，因为gcd的数量很少，所以很快。枚举是存在一个新的map里，枚举完了以后，和老的map交换，因为我们只用上一次所有串，也就是必须用上一个字符，所以只用存上一次的情况就好了，然后把这次每个gcd的数量加进答案。（这里也许可以不用一个单独的map，挖）
#include<iostream>
#include<vector>
#include<map>
#include<cstdio>
#define Mp make_pair
using namespace std;
typedef pair<int,int> pii;
map<int,int>mp;
map<int,int>nextmp;
map<int,long long>ans;
int a[];
int gcd(int a,int b)
{
return b==?a:gcd(b,a%b);
}
int main()
{
int n,q; scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
}
for(int i=;i<=n;i++)
{
nextmp.clear();
for(map<int,int>::iterator it=mp.begin();it!=mp.end();it++)
{
int temp1=a[i],temp2=it->first;
if(temp1<temp2) swap(temp1,temp2);
nextmp[gcd(temp1,temp2)]+=it->second;
}
nextmp[a[i]]++;
swap(mp,nextmp);
for(map<int,int>::iterator it=mp.begin();it!=mp.end();it++)
{
ans[it->first]+=it->second;
}
}
scanf("%d",&q);
for(int i=;i<=q;i++)
{
int x; scanf("%d",&x);
printf("%I64d\n",ans[x]);
}
return ;
}