ABC125 C - GCD on Blackboard

atcoder.jp

値の列に対して二項演算を実行していって値を計算したい。そして、一つ抜いた時の値を計算したい。 この問題で言えば、gcdを実行していくが一つ抜いた時のgcdを高速に計算したい。

この時二項演算が結合則を満たすと、どこから計算していっても良いので左から計算していった配列と右から計算していった配列を用意することで1つ抜いた値を高速に計算できる。わかりにくいので足し算を例にとって説明してみる。値の列

al = [a_1, a_2, ... , a_n]

が与えられたとする。a_i以外を足し合わせた値を高速に計算したいが引き算は使えないとする。足し算はどこから計算していっても大丈夫なので、まずは左からの累積和

ll[i] = a_1 + a_2 + ... + a_i

と右からの累積和

rl[i] = a_i + a_(i+1) + ... + a_n

を計算しておく。こうするとll[i-1]+rl[i+1]でi番目を抜いた値を計算できる。この方法は結合則を満たせば足し算以外でも(gcdでも)使うことができる。