问题描述

在一个神秘的世界中，存在一个传说中的神秘花园，被认为拥有无限的知识。但要进入这个花园，你必须解决花园入口处的一道神秘数学难题。这个难题与一个特殊的数学函数相关，称为“神秘函数”。

神秘函数 S(x)S(x) 的定义如下：

• 当 xx 为 00 时，S(0)=1S(0)=1。
• 当 xx 为偶数时，S(x)=S(x/2)S(x)=S(x/2)。
• 当 xx 为奇数时，S(x)=S(x−1)+1S(x)=S(x−1)+1。

你需要编写一个程序，计算给定正整数 xx，神秘函数 S(x)S(x) 的值。只有当你正确解决了这道难题，才能获得通行证，进入神秘花园探索其中的知识宝藏。

输入格式

输入包含一个正整数 xx（1≤x≤1061≤x≤106），表示你要解决的神秘函数问题。

输出格式

输出一个整数，表示神秘函数 S(x)S(x) 的值，即你成功解决问题后得到的答案。

样例输入

7

样例输出

4

说明

在示例中，你需要计算神秘函数 S(7)S(7) 的值。计算过程如下：

S(7)=S(7−1)+1=S(6)+1=S(6/2)=S(3)+1=S(3−1)+1=S(2)+1=S(2/2)=S(1)+1=1+1=2+1=3+1=4S(7)=S(7−1)+1=S(6)+1=S(6/2)=S(3)+1=S(3−1)+1=S(2)+1=S(2/2)=S(1)+1=1+1=2+1=3+1=4

所以，神秘函数 S(7)S(7) 的值为 44。

评测数据规模

对于 100100% 的评测数据，1≤x≤1061≤x≤106。

运行限制

语言	最大运行时间	最大运行内存
C++	1s	128M
C	1s	128M
Java	2s	128M
Python3	3s	128M

答案解析

#include <iostream>
using namespace std;

long long fi(int n){
  if(n==0) return 1;
  else if(n==1) return 2;
  else if(n==2) return 2; 
  
  if(n%2==0) return fi(n/2);
  else if(n%2!=0) return fi(n-1)+1;
  
  return 0;
}


int main()
{
  int x;cin>>x;
  int z = fi(x);
  cout<<z<<endl;
  return 0;
}