P2235 [HNOI2002] Kathy Function

Tiger likes math very much, so he joined the school's extracurricular math club. In the club, the teacher introduced the Kathy function to Tiger, which is defined as: $$ \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 became very interested in the Kathy function, and through studying he found that many numbers $n$ satisfy $f(n)=n$. Given a number $m$, he wants you to find the number of positive integers $n$ such that $f(n)=n$, where $n \leq m$.

The input contains a single line with an integer $m$.

Output a single integer: the number of positive integers $n$ with $n \leq m$ that satisfy $f(n)=n$.

Constraints For all testdata, it is guaranteed that $1 \leq m \leq 10^{100}$. Translated by ChatGPT 5