Strong Elements solution codechef-

Strong Elements solution codechef

Chef has an array AA of length NN.

An index ii is called strong if we can change the gcd of the whole array just by changing the value of AiAi.

Determine the number of strong indices in the array.

Input Format

  • First line will contain TT, number of test cases. Then the test cases follow.
  • First line of each test case contains an integer NN denoting the size of the array AA.
  • Second line contains NN space separated integers A1,A2,,ANA1,A2,…,AN – denoting the array AA.

Output Format

For each test case, output the number of strong indices in the array.

Strong Elements solution codechef

  • 1T51041≤T≤5⋅104
  • 2N31052≤N≤3⋅105
  • 1Ai1091≤Ai≤109
  • Sum of NN over all test cases do not exceed 31053⋅105.

Sample Input 1 

3
3
5 10 20
4
3 5 7 11
4
2 2 2 2

Sample Output 1 

3
0
4

Strong Elements solution codechef

Test Case 11: All the indices are strong.

  • For index 11 you can change the element to 1010 which changes the gcd of the array to 1010.
  • For index 22 you can change the element to 1212 which changes the gcd of the array to 11.
  • For index 33 you can change the element to 1212 which changes the gcd of the array to 11.

Test Case 22: No index is strong. If you change any single element, gcd still remains the same.

Test Case 33: All the indices are strong. You can change any element to 33. This changes the gcd of the array to 11.

Leave a Comment