Score : $400$ points

问题描述

一个函数 $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)$。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 11:34:54