当前没有测试数据。

D - 又一个递归函数

分数: $400$ points

问题描述

给定一个非负整数 $x$，函数 $f(x)$ 满足以下条件。

• $f(0) = 1$。
• 对于任意正整数 $k$，有 $f(k) = f(\lfloor \frac{k}{2}\rfloor) + f(\lfloor \frac{k}{3}\rfloor)$。

其中，$\lfloor A \rfloor$ 表示将 $A$ 向下取整的整数值。

求解 $f(N)$。

约束

• 整数 $N$ 满足 $0 \le N \le 10^{18}$。

输入

从标准输入中按以下格式输入：

$N$

输出

打印结果。

2

3

我们有 $f(2) = f(\lfloor \frac{2}{2}\rfloor) + f(\lfloor \frac{2}{3}\rfloor) = f(1) + f(0) =(f(\lfloor \frac{1}{2}\rfloor) + f(\lfloor \frac{1}{3}\rfloor)) + f(0) =(f(0)+f(0)) + f(0)= 3$。

0

1

100

55