Problem Link :- PrepBytes
My approach :-
-
I am going to use 2 for loop but with optimization.
-
While traversing in the 2nd loop if gcd equal 1 than for the rest of the subarray gcd will also be 1.
-
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;
}