C - GCD on Blackboardを平方分割で解く

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は高速に求まる

f:id:peroon:20190428135132j:plain

感想

  • 平方分割は単純というイメージがあったが、結構書くのに時間がかかった
  • 自分で作ったテストケースが豊富だったのでバグを取り除けたが、テストケースが少ない場合はバグが取り切れない可能性がある
  • 例えば
    • 最終ブロックで添字を超えてアクセスしてしまう
    • 分割数が不適切 N=15, sqrt(N) = 3 (整数に入れた場合), 本当は4で割りたい
    • など