Xmas Contest 2019 D: Sum of (-1)^f(n) 解説

https://atcoder.jp/contests/xmascon19/tasks/xmascon19_d

問題概要

$n$ の素因数の個数 (重複込み) を $f(n)$ とする． $N$ が与えられるので $\sum_{n=1}^N (-1)^{f(n)}$ を求めよ．

解法 1 (?)

答えを手元で全部計算して，適当な間隔で区切って埋め込みます．狭い区間については区間篩のアルゴリズムで $f$ を効率的に計算できる (素数 $p$ で篩うときに $p$ で割り切れる回数だけ $-1$ 倍する) ので，これで正解することができます．

$45$ 点は割と易しめだと思います． $100$ 点は結構な計算資源を使うかなと思っていたので，解けちゃってもいいかなという感じでした．何なら昔の問題にリンクを貼っていて，パソコンを使いましょうというのを伝えていた感じだったかもしれません．

解法 2

$\lambda(n) = (-1)^{f(n)}$ とおきます．突然ですが，正の整数 $n$ に対し， $\sum_{d|n} \lambda(d)$ は $n$ が平方数のとき $1$ ，そうでないとき $0$ です．理由は例えば $n = 2^3 \cdot 3^4$ なら

    3^0 3^1 3^2 3^3
2^0  +1  -1  +1  -1
2^1  -1  +1  -1  +1
2^2  +1  -1  +1  -1

みたいな感じで多次元の格子点を市松模様で塗るのを考えてみるとわかります． $\lambda$ は Liouville 関数として知られていて，Wikipedia にもこの式は載っています．もうちょっと突然でない導き方については後述します．

さて， $L(N) = \sum_{n=1}^N \lambda(n)$ を求めたいわけですが， $\sum_{d|n}$ みたいなのを見たら累積和をとるという知る人ぞ知る典型テクニックがありまして， $\sum_{n=1}^m \sum_{d|n} \lambda(d) = \sum_{k=1}^m L(\lfloor\frac{m}{k}\rfloor)$ となります ( $\frac{n}{d}$ を先に固定して和をとるとわかります)．一方 $n$ が平方数なら $1$ というのを $1 \le n \le m$ で和をとると $\lfloor\sqrt{m}\rfloor$ なので， $\sum_{k=1}^m L(\lfloor\frac{m}{k}\rfloor) = \lfloor\sqrt{m}\rfloor$ が得られました．これを $L(m) = \lfloor\sqrt{m}\rfloor - \sum_{k=2}^m L(\lfloor\frac{m}{k}\rfloor)$ と書くと $L$ の漸化式を得たことになります．

この形の漸化式をどうするかも知る人ぞ知る典型テクニックなのですが， $L(N)$ を計算するのに必要な $L$ の値は $L(\lfloor\frac{N}{k}\rfloor)$ の形だけになっていて ( $\left\lfloor\frac{\lfloor\frac{N}{k}\rfloor}{k'}\right\rfloor = \lfloor\frac{N}{k k'}\rfloor$ に注意)，異なる $\lfloor\frac{N}{k}\rfloor$ の値は $2 \sqrt{N}$ 通りくらいしかありません． $\sum_{k=2}^m L(\lfloor\frac{m}{k}\rfloor)$ の計算は同じ $\lfloor\frac{m}{k}\rfloor$ の値のものをまとめることで $O(\sqrt{m})$ 時間でできるので，

$1 \le m \le \lfloor\sqrt{N}\rfloor$ について $L(m)$ を求めるのに $O(\sqrt{\sqrt{N}}) \times \sqrt{N} = O(N^{3/4})$ 時間
$1 \le k \le \lfloor\sqrt{N}\rfloor$ について $L(\lfloor\frac{N}{k}\rfloor)$ を求めるのに $O\left(\int_{k=1}^{\sqrt{N}} \sqrt{\frac{N}{k}}\right) = O(N^{3/4})$ 時間

となり，全体で $O(N^{3/4})$ 時間の解法が得られました．実装によりますが $45$ 点の想定です．メモ化再帰で連想配列の類を使うと実行時間がちょっと厳しいかもしれません (配列 $2$ つでできます)．

さらなる高速化ですが，小さい方の答えを定義に戻って計算します．Eratosthenes の篩を用いると $1 \le m \le M$ について $L(m)$ を求めるのが $O(M \log \log M)$ 時間でできます．大きい方は $k \le \frac{N}{M}$ まででよくなって $O(N^{1/2} M^{-1/2})$ 時間になるので， $M = (N / \log \log N)^{2/3}$ くらいにとるのがよく， $O(N^{2/3} (\log \log N)^{1/3})$ 時間解法が得られました (高速な篩を用いれば $O(N^{2/3})$ 時間)．これで $100$ 点です．

Dirichlet 級数

最初に天下った部分の話です． $\lambda$ は乗法的関数なので，(形式的) Dirichlet 級数を考えてみたくなりますね！　Euler 積の形で計算すると， $\sum_{n=1}^\infty \lambda(n) n^{-s} = \prod_{p:素数} (1 - p^{-s} + p^{-2s} - \cdots) = \prod_p \frac{1}{1 + p^{-s}} = \prod_p \frac{1 - p^{-s}}{1 - p^{-2s}} = \frac{\zeta(2 s)}{\zeta(s)}$ となり Riemann の $\zeta$ 関数で表すことができました． $\zeta(s)$ をかけるという操作は $\sum_{d|n}$ をとることに対応していて， $\zeta(2 s)$ は平方数だけ $1$ な級数を表しているので，先ほど使った式が示せました．この辺の話は，例えば maspy さんの HP で丁寧に解説されています．

さっきやった方法は Liouville 関数に限った話ではなく，累積和が簡単に書けている数論的関数を $\zeta(s)$ で割ったもの (つまり，Möbius 変換したもの) の累積和を高速に求める一般的な手法になっています．なので，Möbius 関数 $\mu$ や Euler の $\varphi$ 関数なんかの累積和も同様に高速に求まります (それらのほうがたぶん有名なので， $\mu$ の累積和に帰着させて解くという方針も見られました)．