トーティエント関数$\varphi(i)$の和$\sum_{i=1}^{n}{\varphi (i)}$を$O(n^{2/3}(\log\log{n})^{1/3})$で求めるアルゴリズム

Latest Author 夕叢霧香(ゆうむらきりか) /Date 2018-06-03 12:12:39 / Views 454
2 (Favした一覧ページはユーザーページから)
本項ではオイラーのトーティエント関数$\varphi(i)$の和$\sum_{i=1}^{n}{\varphi (i)}$を$O(n^{2/3}(\log\log{n})^{1/3})$で求めるアルゴリズムを紹介いたします。 オイラーのトーティエント関数$\varphi(i)$は$1$から $i$ までの整数のうち $i$ と互いに素なものの個数と定義します。 このアルゴリズムはプロジェクトオイラーの問題として何度か出題されていますが、 競技プログラミングの問題としては筆者は見たことがありません。他にも、他の界隈では有名だが競技プログラミングの界隈ではあまり知られていないアルゴリズムがたくさんあると思います。そのような問題をどんどん共有したいと思って本稿を書いています。計算量解析についてかならいさんに教えていただきました。感謝いたします。

まず準備として、任意の正の整数$m$について $m = \sum_{dはmの因数}{\quad\varphi(d)}$ を示します。 ここでは$m$との最大公約数が$g$であるものが、$g\times$($m$と互いに素な数)と書けることに注目しましょう。 $g\times$(mと互いに素な数)$≦ m$ですから、$g$にかかる($m$と互いに素な数)は$[m/g]$以下です。 したがって、$m$との最大公約数が$g$となるような数の個数は、$n$と互いに素な数のうち$[m/g]$以下のものの個数と等しくなります。 つまり$\varphi([m/g])$個あります。 ここで $g$ を $m$ の因数すべてについて試して、和をとるとそれは$1$から $n$ までの数すべてに渡って一つずつ数えたのと同じです。 したがって 任意の正の整数について、$m = \sum_{dはmの因数}{\quad\varphi(d)}$となります。

$m = \sum_{dはmの因数}{\quad\varphi(d)}$の $m$ を$1$から $N$ まで変化させたときの和を取り、変形します。
$1+2+...+N = \sum_{dは1の因数}{\quad\varphi(d)}+\sum_{dは2の因数}{\quad\varphi(d)}+...+\sum_{dはNの因数}{\quad\varphi(d)}$
$N(N+1)/2 = \sum_{n=1}^N \sum_{i=1}^{[N/n]}{\varphi(i)}$
$N(N+1)/2 = \sum_{n=2}^N \sum_{i=1}^{[N/n]}{\varphi(i)} + \sum_{n=1}^N {\varphi(n)}$
ここで、オイラーのトーティエント関数$\varphi(i)$を$i=1,2,...,n$まで変化させたときの和を$\Phi(n)=\sum_{i=1}^{n}{\varphi(i)}$と定義します。 すると上の式は
$N(N+1)/2 = \sum_{n=2}^N \Phi([N/n]) + \Phi(N)$
$\Phi(N) = N(N+1)/2 - \sum_{n=2}^{N} \Phi([N/n])$
とできます。ここで、$\Phi(N)$が求めたい値になっています。

ここで $i=1,2,...,N$と変化させたとき、$[N/i]$が高々$2\sqrt{N}-1$個の相異なる数しか取らないことに注意しましょう。 $i$が$\sqrt{N}$以上の時は$[N/i]$は$1$から$\sqrt{N}$ の範囲の数しか取らず、高々$\sqrt{N}$個の相異なる数しか取りません。 また$i$が$\sqrt{N}-1$以下の時は$[N/i]$は$\sqrt{N}+1$から $N$までの数字を取るもののiが1,2,...,$\sqrt{N}-1$の数しかしかとらないので こちらもまた高々$\sqrt{N}-1$個の相異なる値しかとりません。 したがって全体では$[N/i]$は$2\sqrt{N}-1$個の相異なる数しか取りません

$[N/i]$が同じ数をとる項をまとめて計算しましょう。正の整数$k$について、$k=[N/i]$となるような$i$の範囲を$k$の関数として求めます。
$k=[N/i]$
$k≦N/i< k+1$
$N/(k+1) < i ≦ /k$
$[N/(k+1)] < i ≦ [N/k]$
これより、$k=[N/i]$となる$i$は$[N/(k+1)] < i ≦ [N/k]$を満たす整数全てであり、全体で、$[N/k]-[N/(k+1)]$個あると分かりました。

以上から任意の正の整数$m$について、$\Phi(m)$が高々$O(\sqrt{m})$個の$\Phi(i)$ $(i < N)$の線形結合で書けることが分かりました。 ここである正の整数$k$を閾値として設定し、$\Phi(1),\Phi(2),...,\Phi(k)$まで前計算し、それ以上の場合はメモ化再帰で計算することを考えます。 前計算に要する時間は$O(k\log\log{k})$です。これは素数の因数が$p_1,p_2,...,p_t$で表されるような正の整数$n$のトーティエント関数の値が $\varphi(n)=n(1-1/p_1)(1-1/p_2)...(1-1/p_t)$と書けることを用いれば、エラストテネスのふるいの要領で実現できます。 そして再帰の計算量は$O(\sum_{i=1}^{N/k}{(N/i)^{1/2}})=O(N/\sqrt{k})$。 ここで、$k=(N/\log\log{N})^{2/3}$とすると、全体の計算量は$O(n^{2/3}(\log\log{N})^{1/3})$となります。