102753: [AtCoder]ABC275 D - Yet Another Recursive Function
Description
Score : $400$ points
Problem Statement
A function $f(x)$ defined for non-negative integers $x$ satisfies the following conditions.
- $f(0) = 1$.
- $f(k) = f(\lfloor \frac{k}{2}\rfloor) + f(\lfloor \frac{k}{3}\rfloor)$ for any positive integer $k$.
Here, $\lfloor A \rfloor$ denotes the value of $A$ rounded down to an integer.
Find $f(N)$.
Constraints
- $N$ is an integer satisfying $0 \le N \le 10^{18}$.
Input
The input is given from Standard Input in the following format:
$N$
Output
Print the answer.
Sample Input 1
2
Sample Output 1
3
We have $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$.
Sample Input 2
0
Sample Output 2
1
Sample Input 3
100
Sample Output 3
55
Input
题意翻译
## 题目描述 定义函数 $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(x)$。 ## 输入格式 一个整数。 > $ N $ ## 输出格式 一行，一个整数，代表 $f(N)$ 的值。 ## 样例 #1 ### 样例输入 #1 ``` 2 ``` ### 样例输出 #1 ``` 3 ``` ## 样例 #2 ### 样例输入 #2 ``` 0 ``` ### 样例输出 #2 ``` 1 ``` ## 样例 #3 ### 样例输入 #3 ``` 100 ``` ### 样例输出 #3 ``` 55 ``` ## 提示 ### 数据范围 - $ 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 $。Output
得分：$400$分
问题描述
定义一个对于非负整数$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$
输出
打印答案。
样例输入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