問題

提出解答

問題の概要

非負整数 $x$ に対して, $f(x)$ は次のように定義されている.

$f(x)=\begin{cases} 1 & (x=0) \\ f \left( \left \lfloor \dfrac{x}{2} \right \rfloor \right)+f \left( \left \lfloor \dfrac{x}{3} \right \rfloor \right) & (x \gt 0)\end{cases}$

$f(N)$ を求めよ.

制約

$0 \leq N \leq 10^{18}$

解法

再帰を用いて求めることになる. ただ, 何の工夫もなく再帰をすると, $N$ を $2,3$ で割って $0$ にするための方法全てを全探索していることになり, $\dbinom{2 \log_3 N}{\log_3 N}$ 回以上の計算が必要になり, 流石に間に合わない.

しかし, 引数に出てくる整数が整数 $a,b$ を用いて $\left \lfloor \dfrac{N}{2^x 3^y} \right \rfloor$ で表せる整数に限られること, 及び, $f(\bullet)$ は関数なので, 1度計算し, 結果が確定すればそれ以降については同じ引数の場合は計算せずとも結果を返せることを利用する.