You are given an array A of size N. You have to find the number of subarrays with gcd equal to K. Constraints : 1) 1 <= n <= 1e3 , 2) 0 <= A[i] <= 1e9 and 3) 1 <= K <= 1e9

I solved this question using brute force in O(N*N*log(N)) complexity. But I am just curious if there is any O(N*logN) solution to solve it. I have searched for sometime but could not find anything. Can someone pls tell if there is any way to do it O(N*logN)? Thanks.