A counting subarray problem

Правка en4, от I_am_Noobieee, 2024-09-16 14:29:16

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.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en7 Английский I_am_Noobieee 2024-09-16 14:32:39 10
en6 Английский 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 Английский I_am_Noobieee 2024-09-16 14:30:13 12
en4 Английский I_am_Noobieee 2024-09-16 14:29:16 19 Tiny change: '= n <= 1e3\n 2) 1 <= ' -> '= n <= 1e3 and 2) 1 <= '
en3 Английский I_am_Noobieee 2024-09-16 14:28:51 4 Tiny change: ' ' -> ' '
en2 Английский I_am_Noobieee 2024-09-16 14:28:30 6
en1 Английский I_am_Noobieee 2024-09-16 14:27:53 452 Initial revision (published)