### FunnyScientist's blog

By FunnyScientist, 7 years ago,

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.

• +8

 » 7 years ago, # | ← Rev. 2 →   +11 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.
•  » » 7 years ago, # ^ | ← Rev. 2 →   +5 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); } 
•  » » » 7 years ago, # ^ |   -8 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.
•  » » » 7 years ago, # ^ | ← Rev. 2 →   +10 you can compute in using Sparse Table data structure (instead of Segment Tree).
•  » » » » 7 years ago, # ^ | ← Rev. 2 →   +10 Thank mukel and JuanMata a lot, I implemented RMQ with Sparse Table with the help of tutorial in TopCoder and it works much more efficiently than Segment Tree! I actually learned several new techniques :D
•  » » 12 months ago, # ^ |   0 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. sort your sequence, with min number going first. e = 0, d = a[0] d = gcd(d, a[last-e]), ++e if e > 0 goto previous step 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; } 
•  » » 11 months ago, # ^ |   0 Can you please explain me in detail , how binary search is helping us in calculation the position r where gcd(i,r) < A[i] .
 » 13 months ago, # | ← Rev. 3 →   -25 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.
•  » » 13 months ago, # ^ |   +36 This problem is from an ongoing contest.
•  » » » 12 months ago, # ^ |   0 Which contest was that? Can you please share a link?
•  » » » » 12 months ago, # ^ |   +12 HackerEarth circuits which happened 2 weeks ago.
•  » » » » » 12 months ago, # ^ |   0 Thanks a lot! It's a great problem by the way!
 » 12 months ago, # | ← Rev. 2 →   +2 Yeah ! my idea is mostly the same as discussed above. And here my code goes -->https://ide.codingblocks.com/s/135466Although i have added comments to make my code readable.
•  » » 12 months ago, # ^ |   +3 A similiar problem on Codeforces.
 » 12 months ago, # |   0 Can you please share the problem source?
•  » » 12 months ago, # ^ |   0 Will you explain me the solution of above problem?