Problem7355--ABC275 —— D - Yet Another Recursive Function

7355: ABC275 —— D - Yet Another Recursive Function

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

SubmitSolved: 1Submit Num: 1StatisticsShowOff!

Description

A function f(x) defined for non-negative integers xx 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).

Input

The input is given from Standard Input in the following format:
$N$

Output

Print the answer.

Constraints

N is an integer satisfying $0 \le N \le 10^{18}$.

Sample 1 Input 

2

Sample 1 Output 

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 2 Input 

0

Sample 2 Output 

1

Sample 3 Input 

100

Sample 3 Output 

55

Source/Category

 
Submit