#P2235. [HNOI2002] Kathy函数

    ID: 1191 远端评测题 1000ms 125MiB 尝试: 3 已通过: 3 难度: 6 上传者: 标签>动态规划dp高精度2002各省省选湖南数位 dp

[HNOI2002] Kathy函数

题目描述

Tiger 非常喜欢数学,所以他参加了学校组织的数学课外兴趣小组。在兴趣小组的学习当中,老师向 Tiger 介绍了 Kathy 函数,Kathy 函数是这样定义的:

$$\left\{ \begin{aligned} &f(1)=1\\ &f(3)=3\\ &f(2n)=f(n)\\ &f(4n+1)=2f(2n+1)-f(n)\\ &f(4n+3)=3f(2n+1)-2f(n) \end{aligned} \right. $$

Tiger 对 Kathy 函数产生了浓厚的兴趣,他通过研究发现有很多的数 nn 都满足 f(n)=nf(n)=n

对于一个给定的数 mm,他希望你求出所有的满足 f(n)=nf(n)=n 的正整数 nn 的个数,其中 nmn\leq m

输入格式

输入只有一行一个整数,表示 mm

输出格式

输出一行一个整数,表示 nn

5
3

提示

数据规模与约定

对于全部的测试点,保证 1m101001 \leq m \leq 10^{100}