To be Calculated
Chef has an array A of length N.
An index i is called strong if we can change the gcd of the whole array just by changing the value of A_i.
Determine the number of strong indices in the array.
Observation 1: GCD of any number with 1 is 1.
In case the gcd of whole array is not 1, then it means that none of its elements is 1, so we can change any element to 1, to make the gcd of the whole array as 1, thus all n indices would be strong indices in this case.
For the case when gcd of the array is 1, let us define two arrays as prefix\_gcd and suffix\_gcd, where
Now we iterate over all the indices of the array and for a particular index say, i, if gcd(prefix\_gcd[i-1],suffix\_gcd[i+1]) is equal to 1 then no matter what the value of A_i, it can’t change the value of gcd of the whole array (which would be 1), so it won’t be a strong index else in any other case it will be a strong index, because we can set A_i to be gcd(prefix\_gcd[i-1],suffix\_gcd[i+1]), and that will become the gcd of the whole array.
O(N), for each test case.