Minimum index Array Product Given an array A(1 indexed based) of positive  integers.For each element A[i] find the minimum index (say idx) such that the product of all the elements from index 1 to idx is divisible by A[i].where(1&lt;=idx&lt;=i).

constraints are: the number of elements of the array 1&lt;=n&lt;=10^5 and

1&lt;=A[i]&lt;=10^5.

For example let A[]={2,4,6,8}

The output should be {1,2,3,2}

I could only think of O(n^2) solution but that gives a T.L.E.

I also looked up to the code of successfully accepted solution but could not understand the logic.I only understood that it is first calculating the smallest prime factor using seive and then calculating the prime factors of each A[i] using its smallest prime factor.However I am not able to understand the later part of the solution.

Here is the code of one of the accepted solution.

int main() {

ll n,arr[500001],minP[500001];
cin&gt;&gt;n;
for(int i=0;i&lt;n;i++){
    cin&gt;&gt;arr[i];
}
for(int i=2;i&lt;=500000;i++){
    minP[i]=i;
}
for(ll i=2;i*i&lt;=500000;i++){
    if(minP[i]==i){
        for(ll j=i*i;j&lt;=500000;j+=i){
            minP[j]=min(minP[j],i);
        }
    }
}
vector&lt;ll&gt; v[500001];
for(int i=0;i&lt;n;i++){
    ll temp = arr[i],mx=0;
    while(temp&gt;1){
        v[minP[temp]].push_back(i);
        temp/=minP[temp];
    }
    temp = arr[i];
    while(temp&gt;1){
        ll x=minP[temp],cnt=0;
        while(temp%x==0){
            temp/=x;
            cnt++;
        }
        mx=max(mx,v[x][cnt-1]);
    }
    cout&lt;&lt;mx+1&lt;&lt;" ";
}


}

Also,Suggest me some relevant material to understand the underlying concept used above. 

Here I have tried to implement the solution using binary search can anybody point the error as I am still getting the wrong answer upon submission.

 void Bsearch(int low,int high,int key,long long product[])
    {

    int ans;
    int mid;
    long long midVal;
    while (low &lt;= high) 
    { 
    mid = low + (high - low + 1) / 2; 
    midVal = product[mid]; 

    if (midVal% key!=0) 
    { 
        low = mid + 1; 
    } 
    else if (midVal%key==0) 
    { 
        ans=mid;
        high=mid-1; 
    } 
} 
     cout&lt;&lt;ans+1&lt;&lt;" ";
} 
  int main()
  {
int n;
cin&gt;&gt;n;
int arr[n];
long long product[n];
int i;
for(i=0;i&lt;n;i++)
cin&gt;&gt;arr[i];
product[0]=arr[0];
for(i=1;i&lt;n;i++)
product[i]=product[i-1]*arr[i];//prefix product array
for(i=0;i&lt;n;i++)
{
    int temp=arr[i];
    Bsearch(0,n-1,temp,product);//Using binary search to find the minimum 
                                  index.
}
}
Here's a simple $O(n \log n)$ solution if multiplication and the modulus operator is always assumed to be $O(1)$ (which is a big assumption -- see the note at the end).

Create a new array, $B$, in which the first element is $A[1]$ and every future element at index $i \in 2..n$ is $A[i] * B[i-1]$. This gives you an array of all "partial products".

This array is nondecreasing, and $B[j]$'s factors are a superset or $B[i]$'s factors whenever $i &lt; j$. Therefore, for any $A[i]$ (or even for every integer $k$), you can use binary search to find the smallest index $i$ for which $k$ divides $A[1] * A[2] ... * A[i]$. This takes $O(\log n)$ time per lookup, or $O(n \ log n)$ in total for all of $A$.

--

Regarding the initial assumption. As it turns out, assuming arithmetic operations can be done in constant time gives you a bit more power than what most people consider reasonable. For example, one can factor arbitrary integers in polynomial time under this assumption, by constructing pathologically large multiplications/divisions that let them "carpool" many different operations into one. Do you know which cost model we are operating under?