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 and 2) 1 <= A[i], K <= 1e9

I solved this question using brute force in O(N*N*log(N)) complexity. But I am just curious if there any O(N*logN) solution for 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.