Sum of GCD of all contiguous subsequence

→ Обратите внимание

До соревнования
Codeforces Round 1099 (Div. 2)
2 дня
Зарегистрироваться »

*есть доп. регистрация

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	Benq	3792
2	VivaciousAubergine	3647
3	Kevin114514	3611
4	jiangly	3583
5	strapple	3515
6	tourist	3470
7	Radewoosh	3415
8	Um_nik	3376
9	maroonrk	3361
10	XVIII	3345

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	Qingyu	162
2	adamant	148
3	Um_nik	146
4	Dominater069	143
5	errorgorn	141
6	cry	138
7	Proof_by_QED	136
8	YuukiS	135
9	chromate00	134
10	soullless	133

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя FunnyScientist

Sum of GCD of all contiguous subsequence

Автор FunnyScientist, 12 лет назад, По-английски

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.

FunnyScientist
12 лет назад
17

Комментарии (14)

Показать архивные | Написать комментарий?

pzajec

12 лет назад, скрыть # |

← 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.

→ Ответить

FunnyScientist

12 лет назад, скрыть # ^ |

← Rev. 2 →

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);
}

→ Ответить

mukel

12 лет назад, скрыть # ^ |

-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.

→ Ответить

JuanMata

12 лет назад, скрыть # ^ |

← Rev. 2 →

+10

you can compute $\text{[math]}$ in $\text{[math]}$ using Sparse Table data structure (instead of Segment Tree).

→ Ответить

FunnyScientist

12 лет назад, скрыть # ^ |

← 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

→ Ответить

leVi_

7 лет назад, скрыть # |

← 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.

→ Ответить