F - x = a^b Editorial
by 
Kiri8128
直接係数を求める方法
包除原理を使わず直接的に係数を求める方法を紹介します。
\(1\) は必ず条件を満たすので、 \(2\) 以上で条件を満たすものを数えます。「\(k\) 乗数」を、ある整数 \(a\) に対して \(a^k\) の形で表せる整数とします。「ちょうど \(k\) 乗数」を「\(k\) 乗数であり、かつ \(2 \le l<k\) に対して \(l\) 乗数ではない数」とします。
\(2\) 以上 \(N\) 以下の \(k\) 乗数の個数を \(f(k)\)（\(= \lfloor\sqrt[k]{N}\rfloor-1\)）、\(2\) 以上 \(N\) 以下のちょうど \(k\) 乗数の個数を \(g(k)\) とすると、求めるものは \(\displaystyle\sum_{k=2}^{\infty} g(k)\) です（制約から、 \(k\) は \(60\) 程度まで見れば十分です）。 また \(f(k)=g(k) + g(2k) + g(3k) + \cdots\) です。
\(f(k)\) たちに適当な係数をかけて足し合わせることで、 \(g(k)\) たちの係数がすべて \(1\) になるようにしたいですが、これは \(k\) の昇順に決めていけば自然に決まります。
イメージ
$k=12$ まで調べる際の係数の決め方のイメージです。 各 $k$ について、 $g$ の係数が $1$ になるように $f$ の係数を決めています。決めた部分は $*$ 印で表しています。
$k=2$ まで足した状態 $$ \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline k & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ \hline f の係数 & 0 & *1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline g の係数 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ \hline \end{array} $$ $k=3$ まで足した状態 $$ \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline k & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ \hline f の係数 & 0 & 1 & *1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline g の係数 & 0 & 1 & 1 & 1 & 0 & 2 & 0 & 1 & 1 & 1 & 0 & 2 \\ \hline \end{array} $$ $k=4$ まで足した状態 $$ \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline k & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ \hline f の係数 & 0 & 1 & 1 & *0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline g の係数 & 0 & 1 & 1 & 1 & 0 & 2 & 0 & 1 & 1 & 1 & 0 & 2 \\ \hline \end{array} $$ $k=5$ まで足した状態 $$ \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline k & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ \hline f の係数 & 0 & 1 & 1 & 0 & *1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline g の係数 & 0 & 1 & 1 & 1 & 1 & 2 & 0 & 1 & 1 & 2 & 0 & 2 \\ \hline \end{array} $$ $k=6$ まで足した状態 $$ \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline k & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ \hline f の係数 & 0 & 1 & 1 & 0 & 1 & {*}\ {-1} & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline g の係数 & 0 & 1 & 1 & 1 & 1 & 1 & 0 & 1 & 1 & 2 & 0 & 1 \\ \hline \end{array} $$ $k=7$ まで足した状態 $$ \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline k & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ \hline f の係数 & 0 & 1 & 1 & 0 & 1 & -1 & *1 & 0 & 0 & 0 & 0 & 0 \\ \hline g の係数 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 2 & 0 & 1 \\ \hline \end{array} $$
posted:
last update: