問題文

次のように定義される関数 f(n) があります。

\[ f(n)=\begin{cases} 1 & (n=0のとき)\\ f\!\left(\left\lfloor\frac{n}{2}\right\rfloor\right) + f\!\left(\left\lfloor\frac{n}{3}\right\rfloor\right) + f\!\left(\left\lfloor\frac{n}{5}\right\rfloor\right) & (n\geq 1のとき) \end{cases} \]

\lfloor x \rfloor は x を整数に切り捨てた値を表します。例えば \lfloor 2.718 \rfloor=2、\lfloor 3 \rfloor=3 です。

正整数 N が与えられるので f(N) を求めてください。

制約

• 1 \le N \le 10^{18}
• N は整数

入力例1

3

出力例1

7

f(3)=f(1)+f(1)+f(0)=(f(0)+f(0)+f(0))+(f(0)+f(0)+f(0))+1=7 となります。

入力例2

987654321098765

出力例2

5977712553952371

ヒント

テスト入出力

書いたプログラムが AC にならず、原因がどうしてもわからないときだけ見てください。

1

3

1000000000000000000

7551346630825729459

解答例

必ず自分で問題に挑戦してみてから見てください。

from functools import cache

@cache  # メモ化
def f(n):
    if n == 0:
        return 1
    return f(n//2) + f(n//3) + f(n//5)

N = int(input())
print(f(N))