# PROBLEM LINK:

Contest Division 1

Contest Division 2

Contest Division 3

Contest Division 4

Setter: Utkarsh Gupta

Tester: Abhinav Sharma, Nishank Suresh

Editorialist: Pratiyush Mishra

# DIFFICULTY:

To be Calculated

# PREREQUISITES:

None

# PROBLEM:

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.

# EXPLANATION:

**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.

# TIME COMPLEXITY:

O(N), for each test case.

# SOLUTION:

Editorialist’s Solution

Setter’s Solution

Tester1’s Solution

Tester2’s Solution