yukicoder No.983 Convolution

bitwise and の代わりにgcdで表す。

包除原理より

$ B_k

$ =\sum_{gcd(i,j)=k} A_i A_j

$ =\sum_{d,i,j} A_{kdi}A_{kdj} \mu(d)

$ =\sum_{d} \mu(d)(\sum_{kd|i} A_{i})^2

$ =\sum_d \mu(d) C_{kd}

補題：ゼータ（またはメビウス）変換前後で列の最大公約数は変化しない。

証明：

$ U_k=\sum_{k|i} V_i であるから、Vの最大公約数はUの最大公約数を割り切る。

また、$ V_k=\sum_{d} \mu(d) U_{kd} だからUの最大公約数はVの最大公約数を割り切る。従ってUの最大公約数とVの最大公約数は一致する。

補題から、Bの最大公約数はCの最大公約数と等しい。

もう一度補題を用いることでCの公約数はAの公約数の二乗に等しい。

よってBの最大公約数はAの公約数の二乗となる。