分数: 400 点
问题陈述
一个函数 f(x) 为非负整数定义 x 满足以下条件。
- f(0) = 1.
- f(k) = f(\lfloor \frac{k}{2}\rfloor) + f(\lfloor \frac{k}{3}\rfloor) 对于任何正整数 k.
在这里, \lfloor A \rfloor 表示的值 A 向下舍入为整数。
查找 f(N).
约束
- N 是满足以下条件的整数 0 \le N \le 10^{18}.
输入
输入由标准输入按以下格式给出:
N
输出
打印答案。
示例输入 1
2
示例输出 1
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.
示例输入 2
0
示例输出 2
1
示例输入 3
100
示例输出 3
55