![解法
● 次に i を動かす
● 約数の個数を
cnt[d] := ( d を約数にもつ数がいくつあるか )
という配列で管理する
● i++ すると、考慮すべき数から i が消えて i+W が
増える
? なので、cnt の更新があるのは i の約数と i+W の約数
だけ
? 毎回約数を計算しなおしても、全体で O(n^1.5) となり
間に合う](https://image.slidesharecdn.com/gcd-130313021505-phpapp01/85/Gcd-6-320.jpg)
Gcd
- 1. Sliding GCD 原案 : fura2 解答 : lyoz, fura2 解説 : fura2
- 2. 問題概要 ● 1, 2, 3, …, N と自然数が並んでいる。 連続する W 個 ( i, i+1, …, i+W-1 ) に注目する ● W 個から好きなだけ選んで GCD (最大公約数) を 計算する ● GCD の値としてありうる数は何種類あるか? すべての i について求めよ
- 3. 解法 ● とりあえず i を固定したときを考える。 S := { i, i+1, …, i+W-1 } とおく ● S から部分集合 T を選んだとする。 GCD(T) としてどんな数が作れるだろうか?
- 4. 解法 ● もちろん i, i+1, …, i+W-1 は作れる。( |T| = 1 の ケース ) ● それ以外については、実は次がいえる : d が作れる ? S が d の倍数を二つ以上含む ● このことから、i, i+1, …, i+W-1 の約数を全部列挙 して、二回以上現れる数を数えれば答えがわかる
- 5. 解法 d が作れる ? { i, i+1, …, i+W-1 } が d の倍数を二つ以上含む ● 証明 (?) 明らか (<=) { i, i+1, …, i+W-1 } に含まれる連続する d の倍数を kd, (k+1)d とすると、 GCD(kd, (k+1)d) = d?GCD(k, k+1) = d となるからOK
- 6. 解法 ● 次に i を動かす ● 約数の個数を cnt[d] := ( d を約数にもつ数がいくつあるか ) という配列で管理する ● i++ すると、考慮すべき数から i が消えて i+W が 増える ? なので、cnt の更新があるのは i の約数と i+W の約数 だけ ? 毎回約数を計算しなおしても、全体で O(n^1.5) となり 間に合う
- 7. ちなみに ● O(n log n) でも解けます ● 興味がある人は考えてみてください
- 8. 提出状況 ● AC Rate – 26.53 % (13/49) ● First Acceptance – Onsite: magyorin (26 min) – All: magyorin (26 min)