Can anyone share hint/approach how to solve this problem.
problem link - link text
https://www.codechef.com/viewsolution/14380212
Have a look at it.Its quite easy I guess. If you don’t understand any part ask
1 Like
can u please elaborate what you did , because its quite tough getting through other’s code . it will be better if you just say what to do ?
what I did is I made an array of size 1001 which keeps the track where any prime was found for the last time… means in ith iteration if I encounter 2 I will set primearr[2]=I. Now suppose I am at some jth iteration and arr[j] has factors p1,p2,p3 say. Now if I have already encountered them previously say at kth iteration then I cant form any continuous subarray from k to j. like this we find for every element what is the minimum index k from which we can form a subarray k to j. Then just count all such subarrays
1 Like
example suppose I have 2,3,4,5,6. Now when I visit 2 I make primearr[2]=0 and startindex[1] remains 0 as I haven’t encountered a common factor yet. when I visit 3 I set primearr[3]=1 and startindex[2] remains 0. Now I come to 4 which is 2*2. Now when I take first 2 I get seen=1 as it was first encountered at position 1. Then when I go for second 2 primearr[2] has already been set to 3.So seen becomes 3 and this startindex[3]=3 i.e it cant form a continuous subarray. Now go to 5. primearr[5]=0. But for this we don’t set startindex[4]=0 as startindex[3]>0 so we cant form continuous subarray.so startindex[4] becomes equal to startindex[3].Similarly for 6 startindex[5]=startindex[3]. Had there been another element say 8 then startindex[6] would be 5 as arr[5] i.e. 6 has a common factor with 8
2 Likes
in case the above link doesn’t show use : xMR08s - Online C++0x Compiler & Debugging Tool - Ideone.com
1 Like
and if this helps you please do upvote. 
and if u face any prblm feel free to ask
also minimum index for array[i] cant be less than minimum index found for array[i-1]…
yes that’s what I explained in the example… 