Need help in a GCD problem

Revision en1, by Lakh, 2018-05-22 19:05:11

I am solving the following problem:

Given an array of N (N<=5*10^5) numbers. Consider the GCD of all the subarrays and print the no. of distinct GCD's found over all subarrays. A[i]<=10^18.

I am using the fact that for a fixed element A[i], GCD decreases as we increase the subarray length starting from element A[i]. So I considered all subarrays starting from index i and using binary search + sparse matrix(for range gcd) computed the indices where GCD changes and inserted the GCDs in a set and did the same for all other indices. But getting TLE. Please suggest some optimization or some other approach for this problem.

My code: https://ideone.com/zeDVkD

Tags array, gcd

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Lakh 2018-05-22 19:05:11 697 Initial revision (published)