本文共 903 字，大约阅读时间需要 3 分钟。
1 #include 2 #include 3 #include 4 #include 5 using namespace std; 6 map ans; 7 pair mp1[100005]; 8 pair mp2[100005]; 9 int a[100005];10 int gcd(int x,int y)11 {12 if (y==0) return x;13 return gcd(y,x%y);14 }15 int main()16 {17 int n,i,j,pre=0,now,q,temp;18 scanf("%d",&n);19 for (i=1;i<=n;i++) scanf("%d",&a[i]);20 for (i=1;i<=n;i++)21 {22 now=1;23 mp2[now]=make_pair(a[i],1);24 for (j=1;j<=pre;j++)25 {26 temp=gcd(mp1[j].first,a[i]);27 if (mp2[now].first==temp) mp2[now].second+=mp1[j].second;28 else mp2[++now]=make_pair(temp,mp1[j].second);29 }30 pre=now;31 for (j=1;j<=now;j++) {32 mp1[j]=mp2[j];33 ans[mp1[j].first]+=mp1[j].second;34 }35 }36 scanf("%d",&q);37 while (q--)38 {39 scanf("%d",&j);40 printf("%I64d\n",ans[j]);41 }42 }
转载于:https://www.cnblogs.com/xiao-xin/articles/4012033.html