Codeforcesラウンド671ディビジョン1 C（アレイの究極wierdness）

Question

Codeforces 671ディビジョン1 C（アレイの究極wierdness）

BK ... VIはB1、B2、B3とします。私たちのl - rは少なくともこのインデックスの k - 1をカバーしなければならないことに注意してください。 lはb2以下でなければなりません。

私は解決策の最初の部分を理解することができましたが、誰かが上記の説明を説明することができます。あなたのため、適切ではない、その後

editorial link

Answer 1

範囲 [l, r]の外にある yな bxと byこと

(l-r)未満k-1インデックスをカバーする場合、その後、xがなければならないので、と理由i | a[bx], i | a[by]、gcd(a[bx], a[by]) >= i、 nextをiからi-1に更新しています。 (l-r)がb1, ..., bkの少なくともk-1要素を覆うため

のでlはb2以下でなければなりません。

Answer 2

define F（l、r）の値はA [1：n]の部分列を示します。

A [1 ...（L-1）、（R + 1）...]最大GCDを計算する（[I]、A [J]）

---