← 返回题目列表

AtCoder · abc275_d

G. 又一个递归函数

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

一个函数 f(x) 为非负整数定义 x 满足以下条件。

  • f(0) = 1.
  • f(k) = f(\lfloor \frac{k}{2}\rfloor) + f(\lfloor \frac{k}{3}\rfloor) 对于任何正整数 k.

在这里, \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