FunnyScientist's blog

Sum of GCD of all contiguous subsequence
By FunnyScientist, 12 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

Comments Comments (14)
| Write comment?
»
12 years ago, hide # |
← 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.

→ Reply
  • »
    »
    12 years ago, hide # ^ |
    ← 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);
}
    → Reply
»
7 years ago, hide # |
← 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.

→ Reply
»
7 years ago, hide # |
← 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.

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

Can you please share the problem source?

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

    Will you explain me the solution of above problem?

    → Reply