FunnyScientist's blog

By FunnyScientist, 6 years ago, In English,

I'm learning number theory and I cannot figure out the solution of following problem:

Given an array of integer A with N element with constrains N <= 10^5, A[i] <= 10^12. We call GCD(L, R) is greatest common divisor of all element A[L], A[L + 1], ..., A[R]. Return the sum of all contiguous sub-sequence in A.

I did have some idea that, for fixed index i, the value of GCD(i, j) will be decreasing as GCD(i, j) >= GCD(i, j + 1). Also, because GCD(i, j + 1) must be equal or divisor of GCD(i, j), the number of distinct value X of GCD(i, j), GCD(i, j + 1), ..., GCD(i, N) will satisfies 2^X <= A[i].

But I cannot go further. Please give me some more insights.

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

»
6 years ago, # |
Rev. 2   Vote: I like it +11 Vote: I do not like it

Yes, for every i GCD decreases at most lg(A[i]) times. If you could calculate GCD(i,r) for any fixed r fast enough, then you could find all the positions where GCD changes using binary search.

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

    Thank you very much. Value GCD(i,r) can be computed by using Segment Tree in Log2(N), but I found that for N = 1e5 and large A[i] it somehow still slow. Is there any more efficient method for query operation? Currently it looks like that:

    ll query(int node, int l, int r, int i, int j)
    {
    	if(r < i || j < l)
    		return -1;
    	if(i <= l && r <= j)
    		return it[node];
    	ll p1 = query(Lc, i, j);
    	ll p2 = query(Rc, i, j);
    	if(p1 == -1) return p2;
    	if(p2 == -1) return p1;
    	return gcd(p1, p2);
    }
    
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      You can use RMQ, but instead of min/max use gcd. Queries can be answered with only one gcd call. Make sure to use a fast gcd implementation.

    • »
      »
      »
      6 years ago, # ^ |
      Rev. 2   Vote: I like it +10 Vote: I do not like it

      you can compute in using Sparse Table data structure (instead of Segment Tree).

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Several days ago there was a task similar to yours. It was requested to find GCD among all numbers in sequence a[]. E.g. for gcd({8, 24, 28}) answer is 4.

    Perhaps it will helpfull to you. Below is algorithm for this case, which is O((N-1)*K) where

    • N is sequence length
    • K is complexity of gcd version for pair of numbers.
    1. sort your sequence, with min number going first.
    2. e = 0, d = a[0]
    3. d = gcd(d, a[last-e]), ++e
    4. if e > 0 goto previous step
    5. else return d

    Below is C++ example, perhaps you may find a better gcd(a,b) implementation then below.

    Code:

    int_t gcd(int_t a, int_t b) {
      // a > 0, b > 0
      while (b) {
        int_t m = a % b;
        a = b;
        b = m;
      }
      return a;
    }
    
    int_t gcd(int_t *a, int_t *e) {
      int_t res = *a;
      for (int_t *c = e, *s = a+1; c != s;) {
        --c;
        res = gcd(*c, res);
      }
      return res;
    }
    
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please explain me in detail , how binary search is helping us in calculation the position r where gcd(i,r) < A[i] .

»
3 months ago, # |
Rev. 3   Vote: I like it -25 Vote: I do not like it

I came across a similar question recently in which I have to find the sum of GCD's of all subarrays.

I know that GCD decreases at most log(A[i]) times so I can find all the positions where GCD decrease using Binary Search and sparse table but I am unable to think that how should I find the sum of GCD's of all subarrays from range L to R.

My approach is O(nlogn) for a single query, can it be done faster and more efficiently if there are multiple queries?

ex- A = [2,3,4,5]

L = 1, R = 4 (1-indexed)

ans = 20.

»
2 months ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

Yeah ! my idea is mostly the same as discussed above. And here my code goes -->

https://ide.codingblocks.com/s/135466

Although i have added comments to make my code readable.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you please share the problem source?