 My approach :-

1. I am going to use 2 for loop but with optimization.

2. While traversing in the 2nd loop if gcd equal 1 than for the rest of the subarray gcd will also be 1.

3. After the completion of 1st loop if we got gcd as g . Then for the next iteration of 1st loop if gcd gets equal to g again than for the rest of the traversal of 2nd loop gcd will be g.

My Code :-

``````#include <bits/stdc++.h>
using namespace std;

int findgcd(int a,int b)
{

if(a==0)
return b;
return(findgcd(b%a,a));

}

int main()
{

int n; cin>>n ;
vector<int>v(n);
for(int g=0;g<n;g++)
{
cin>>v[g];
}

int gcd;
unordered_map<int,int> map;
int pass=-1; // concept of pass
// if for the first pass you get p1 than for the
// second pass if you reach p1 than you will get all
// the rest as p1 .

for(int i=0;i<n;i++)
{ gcd=v[i];
map[gcd]++;
for(int j=i+1;j<n;j++)
{
gcd=findgcd(gcd,v[j]);

if(gcd==1)
{
int rest=n-j;
map[gcd]+=rest;
break;
}

if(i!=0)
{
// concept of pass
if(gcd==pass)
{
int rest = n-j;
map[gcd]+=rest ;
break;
}

}

map[gcd]++;
}
pass=gcd;

}
/*  cout<<"content of map "<<endl;
for(auto x : map)
{
cout<<x.first<<" "<<x.second<<endl;
}
cout<<endl;
*/
int q; cin>>q;
for(int i=0;i<q;i++)
{
int val; cin>>val;

cout<<map[val]<<endl;

}

return 0;
}
``````