/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 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
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