メモ

yukicoderでゆるふわgolf

約数包除2

テクニック

https://atcoder.jp/contests/arc185/editorial/11160

今まで何回も見たことあるんだけど、ちゃんと分かっておらず雰囲気でやっていた部分についてを完全に理解することができたのでメモ。

$\sum_n w(n)f(g(n))$ を求めたい。これを $\sum_x f(x) \sum_{g(n)=x}w(n)$ に置き換えて計算するとき、xで累積和を取って $\sum_x h(x) \sum_{x\mid g(n)}w(n)$ とするときの、h ってなんですかという話。
まあ「右側をゼータ変換したんだから左側はメビウス変換でしょ、部分積分なんだから」という気持ちはあるし、 $\sum_{g(n)=x}w(n)$ の寄与を数えるだけでももちろん示せるんだけど、見通しよくやりましょう。

ゼータ変換(に対応する行列)を Z とし、 $\delta_k$ を k 番目の要素が1で他が0の数列とする。

$\sum_n w(n)f(g(n))\\ =\sum_n w(n)\langle f,\delta_{g(n)}\rangle\\ =\sum_n w(n)\langle Z^{-1}f,Z^\top\delta_{g(n)}\rangle$

ゼータ変換が約数側の和を取る操作であるのに対し、 $Z^\top$ は倍数側の和を取る操作になる(伝われ)ので、 $Z^\top\delta_{g(n)}$ は g(n) の約数のところだけ1になる数列である。よって

$=\sum_n w(n)\sum_{x\mid g(n)} (\mu * f)(x)\\ =\sum_{x} (\mu*f)(x) \sum_{x\mid g(n)}w(n)$

具体例

$\sum_{x\leq N}F(x)=\sum_{x\leq N}(\mu*F)(x)\left\lfloor\frac{N}{x}\right\rfloor$

$f=F, g=\mathrm{id}, w=\zeta$ として得られる。

具体例2(冒頭の問題)

$\sum_k 2^k \gcd(A_k,X) = \sum_d \phi(d) \sum_{d\mid \gcd(A_k,X)}2^k$

$f=\mathrm{id}, g(k)=\gcd(A_k,X), w(k)=2^k$ として得られる。

具体例3(約数包除原理)

$\sum_{\gcd(x,y)=1}F(x,y) = \sum_d \mu(d) \sum_{x,y}F(dx,dy)$

$f=\delta_1, g=\gcd, w=F$ として得られる