perogram

平方分割

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)で配列を分割し、ブロックと呼…