seuOJ9163 - 数的转化

• 题目类型：传统
• 输入文件：标准输入流
• 输出文件：标准输出流
• 时间限制：1000 ms
• 空间限制：256 MiB
• 题目标签：Div.2, 2025 帆软杯

题目描述

$998244353$ 是算法竞赛中的常见模数。在算法竞赛中，如果答案特别大，往往会对一个给定的数取模。最近，猪发现，$998244353=119\times 2^{23}+1$，随后便开始痴迷于把正整数写成类似的形式。

给定一个正整数 $N$。可以证明，有无穷多个非负整数三元组 $(a,b,c)$ 满足 $N=a\times2^b+c$。在所有满足上述条件的三元组中，求 $a+b+c$ 的最小值。

输入格式

一行一个整数 $N$（$1\le N<2^{60}$）。

输出格式

一行一个整数，表示答案。

样例

样例 1

输入

1

输出

1

解释

取 $(a,b,c)=(1,0,0)$ 有 $1=1\times2^0+0$，所以 $a+b+c$ 可以是 $1$。

又因为取 $(a,b,c)=(0,0,0)$ 有 $0=0\times2^0+0$，所以 $a+b+c$ 不能是 $0$。

样例 2

输入

998244353

输出

143

解释

取 $(a,b,c)=(119,23,1)$ 有 $998244353=119\times2^{23}+1$，此时 $a+b+c=143$。

可以证明，不存在非负整数三元组 $(a,b,c)$ 满足 $998244353=a\times2^b+c$ 且 $a+b+c<143$。