Lakh's blog

Need help in a GCD problem
By Lakh, history, 6 years ago, In English

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

  • Vote: I like it
  • +2
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
6 years ago, # |
  Vote: I like it +4 Vote: I do not like it

The number of different gcd values of consecutive subsequences headed by A[i] is at most log(n)，so we can save these gcd values for every A[i], the different gcd values generated by A[i+1] are used to update the different gcd values generated by A[i]. so it cost O(nlogn) time complexity and space complexity。

This is an extension of the original problem: You are asked to answer q queries. Each query asks how many different gcd values are in the interval [l,r]。

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    freeloop2 Thanks for the reply . Can you explain this line " the different gcd values generated by A[i+1] are used to update the different gcd values generated by A[i]. so it cost O(nlogn) time complexity and space complexity" a bit more ??

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Different gcd values of consecutive subsequences headed by A[i] equals gcd(A[i], Different gcd values of consecutive subsequences headed by A[i+1] ).

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        freeloop2 Thanks got accepted , didn't know about log(n) factor before this problem. Can you provide the link to the query version of this problem??

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          OK，here is the link: Different GCD Subarry Query have fun!

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it -14 Vote: I do not like it

            It would be very helpful if someone can post editorial for the above problem/similar problem which freeloop2 has provided!!(Different GCD Subarry Query)

            → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you post a link to the question?

→ Reply
»
5 years ago, # |
  Vote: I like it -14 Vote: I do not like it

It seems to me it will help you link.

→ Reply