約数包除原理

$\displaystyle{ \sum_{\substack{(x,y)\in S \\ \gcd(x,y)=1}}f(x,y)=\sum_d \mu(d)\sum_{\substack{(x,y)\in S \\ d\mid\gcd(x,y)}}f(x,y)}$
というだけの話なんですが、これしか頭にないと同じ式変形に毎回一生を費やしてしまうので典型的な用法をメモしておく。

記号
$\mathbb{N}:=\{1,2,\ldots\}$
$[N]:=\{x\in \mathbb{N} \mid x\leq N\}$
$\mu:\mathbb{N}\to\mathbb{R}$ メビウス関数
命題Pに対して $[P]$ をPが真なら1、偽なら0とする（アイバーソンの記法 - Wikipedia）

やりたいこと
$f:\mathbb{N}^2\to \mathbb{R}$ がある。 $\displaystyle F(N):=\sum_{\substack{(x,y)\in [N]^2 \\ \gcd(x,y)=1}}f(x,y)$ を求める。
例えばf=1 のときは実質totient sum

■ O(N)　約数包除
主張
fが次の3条件を満たすとき、F(N)はO(N)で計算できる。

ある $h:\mathbb{N}\to\mathbb{R}$ が存在して任意の(d,x,y)で $f(dx,dy)=h(d)f(x,y)$ が成り立つ。
任意のnで $h(n)$ がO(1)で計算できる
$\displaystyle G(n):=\sum_{\substack{(x,y)\in [n]^2}}f(x,y)$ （gcdの条件がない）について、 $G\left(\left\lfloor\frac{N}{d}\right\rfloor\right)$ の列挙がO(N)

証明
実は $\sum_{d|x}\mu(d)=[x=1]$ が成り立つ。メビウス関数はディリクレ積の意味でゼータ関数の逆元なのでそれはそう。
$\displaystyle{ F(N)=\sum_{\substack{(x,y)\in[N]^2 \\ \gcd(x,y)=1}}f(x,y)\\ =\sum_{(x,y)\in[N]^2}f(x,y)[\gcd(x,y)=1]\\ =\sum_{(x,y)\in[N]^2}f(x,y)\sum_{d\mid\gcd(x,y)}\mu(d)\\ =\sum_{(x,y)\in[N]^2}\sum_{d\mid\gcd(x,y)}f(x,y)\mu(d)\\ =\sum_{1\leq d \leq N}\sum_{\substack{(x,y)\in[N]^2 \\d\mid\gcd(x,y) }}f(x,y)\mu(d)\\ =\sum_{1\leq d \leq N}\mu(d)\sum_{\substack{(x,y)\in[N]^2 \\d\mid\gcd(x,y) }}f(x,y)\\ =\sum_{1\leq d \leq N}\mu(d)\sum_{\substack{(x,y)\in[N/d]^2}}f(dx,dy)\\ =\sum_{1\leq d \leq N}\mu(d)\sum_{\substack{(x,y)\in[N/d]^2}}h(d)f(x,y)\\ =\sum_{1\leq d \leq N}\mu(d)h(d)\sum_{\substack{(x,y)\in[N/d]^2}}f(x,y)\\ =\sum_{1\leq d \leq N}\mu(d)h(d)G\left(\left\lfloor\frac{N}{d}\right\rfloor\right) }$
示せた。*1
$\mu(d)h(d)$ の区間和 $\sum_{\left\lfloor\frac{N}{d}\right\rfloor=x}\mu(d)h(d)$ の列挙を前計算しておくと、GがO(1)で計算できるなら商をまとめるテクを使って本計算は $O(N^{0.5})$ になる。
前計算は2/3乗とかでやることが多い[要出典]

■ O(N)　約数除
こっちのほうが計算量よくなるパターンが一生覚えられないんだよね

主張
fが次の3条件を満たすとき、F(N)はO(N)で計算できる。

ある $h:\mathbb{N}\to\mathbb{R}$ が存在して任意の(d,x,y)で $f(dx,dy)=h(d)f(x,y)$ が成り立つ。
任意のnで $h(n)$ がO(1)で計算できる
$\displaystyle G(n):=\sum_{\substack{(x,y)\in [n]^2}}f(x,y)$ （gcdの条件がない）について、 $G\left(\left\lfloor\frac{N}{d}\right\rfloor\right)$ の列挙がO(N)

証明
$\displaystyle{ F(N)=\sum_{\substack{(x,y)\in[N]^2 \\ \gcd(x,y)=1}}f(x,y)\\ =G(N)-\sum_{\substack{(x,y)\in[N]^2 \\ \gcd(x,y)> 1}}f(x,y)\\ =G(N)-\sum_{2\leq d \leq N}\sum_{\substack{(x,y)\in[N]^2 \\ \gcd(x,y)=d}}f(x,y)\\ =G(N)-\sum_{2\leq d \leq N}\sum_{\substack{(x,y)\in[N/d]^2 \\ \gcd(x,y)=1}}f(dx,dy)\\ =G(N)-\sum_{2\leq d \leq N}\sum_{\substack{(x,y)\in[N/d]^2 \\ \gcd(x,y)=1}}h(d)f(x,y)\\ =G(N)-\sum_{2\leq d \leq N}h(d)\sum_{\substack{(x,y)\in[N/d]^2 \\ \gcd(x,y)=1}}f(x,y)\\ =G(N)-\sum_{2\leq d \leq N}h(d)F\left(\left\lfloor\frac{N}{d}\right\rfloor\right) }$

O(N)かけて予め $h(d)$ の累積和を前計算しておき、区間和 $\sum_{\left\lfloor\frac{N}{d}\right\rfloor=x}h(d)$ をO(1)で取得できるようにしておくとGの計算量次第で本計算部分は $O(N^{3/4})$ になる。
前計算がO(N^0.75)で済むなら、全体でもO(N^0.75)になる。

*1:演習問題：logついてませんか？