Quiz
https://atcoder.jp/contests/abc125/tasks/abc125_c
Submit
https://atcoder.jp/contests/abc125/submissions/5171443
解法
- A[i]を除外した場合の左右のgcdを高速に求めたい
- 累積gcdもいいが、平方分割でも解ける
- sqrt(N)で配列を分割し、ブロックと呼ぶ
- ブロック内部ごとにgcdを求める
- それを使うことで左右のgcdは高速に求まる
感想
- 平方分割は単純というイメージがあったが、結構書くのに時間がかかった
- 自分で作ったテストケースが豊富だったのでバグを取り除けたが、テストケースが少ない場合はバグが取り切れない可能性がある
- 例えば
- 最終ブロックで添字を超えてアクセスしてしまう
- 分割数が不適切 N=15, sqrt(N) = 3 (整数に入れた場合), 本当は4で割りたい
- など