A counting subarray problem

Revision en7, by I_am_Noobieee, 2024-09-16 14:32:39

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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en7 English I_am_Noobieee 2024-09-16 14:32:39 10
en6 English I_am_Noobieee 2024-09-16 14:32:15 19 Tiny change: ' and 2) 1 <= A[i], K <= 1e9\' -> ' and 2) 0 <= A[i] <= 1e9 3) 1 <= K <= 1e9\'
en5 English I_am_Noobieee 2024-09-16 14:30:13 12
en4 English I_am_Noobieee 2024-09-16 14:29:16 19 Tiny change: '= n <= 1e3\n 2) 1 <= ' -> '= n <= 1e3 and 2) 1 <= '
en3 English I_am_Noobieee 2024-09-16 14:28:51 4 Tiny change: ' ' -> ' '
en2 English I_am_Noobieee 2024-09-16 14:28:30 6
en1 English I_am_Noobieee 2024-09-16 14:27:53 452 Initial revision (published)