CODEWITHSUNDEEP
algorithmsegment-tree
shubi_SnowFly
shubi_SnowFly

Reputation: 51

Codeforces Round 671 Div 1 C (ultimate wierdness of array)

Codeforces 671 Div 1 C (ultimate wierdness of array)

Let vi be b1, b2, b3...bk. Note that our l - r must be cover at least k - 1 of this indexes. l must less or equal to b2.

I was able to understand the first part of the solution, but can someone please explain the above statement.

editorial link

Upvotes: 1

Views: 185

Answers (2)

jiang
jiang

Reputation: 41

define F(l,r) value indicate A[1：n] Subsequence.

A[1....(l-1),(r+1)....] to calculate the max gcd(A[i],A[j])

Sum = ∑ ∑F(i,j) (i!=j)

Upvotes: 0

delta
delta

Reputation: 3818

Because if (l-r) covers less than k-1 indexes, then there must be x, y such that bx and by is out of range [l, r], and because i | a[bx], i | a[by], then gcd(a[bx], a[by]) >= i, which is not right, because you are updating next from i to i-1.

Because (l-r) covers at least k-1 elements of b1, ..., bk, so l must be less than or equal to b2.

Upvotes: 2

Related Questions