Yet Another Recursive Function

题目描述

一个函数 $f(x)$ 定义在非负整数 $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$

输出格式

输出答案。

2

3

0

1

100

55

提示

$N$ 是满足 $0 \le N \le 10^{18}$ 的整数。我们有 $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$.

标签: AtCoder|abc275D

来源

AtCoder|abc275D