分数: 300 点
问题陈述
在 AtCoder 上的问题中,经常会要求您:
求模答案 998244353.
在这里,我们有 998244353 = 119 \times 2^{23} + 1。与此相关,解决以下问题:
给你一个整数 N.
打印最小可能值 a + b + c 对于非负整数的三元组 (a, b, c) 满意 N = a \times 2^b + c.
约束
- 1 \leq N \leq 10^{18}
- N 是一个整数。
输入
输入由标准输入按以下格式给出:
N
输出
打印答案。
示例输入 1
998244353
示例输出 1
143
我们有 998244353 = 119 \times 2^{23} + 1,换句话说,三重 (a, b, c) = (119, 23, 1) 满足 N = a \times 2^{b} + c.
值 a+b+c 这个三元组是 143.
没有这样的三元组,其中 a+b+c \leq 142,所以 143 是正确的输出。
示例输入 2
1000000007
示例输出 2
49483
我们有 1000000007 = 30517 \times 2^{15} + 18951,换句话说,三重 (a, b, c) = (30517, 15, 18951) 满足 N = a \times 2^{b} + c.
值 a+b+c 这个三元组是 49483.
没有这样的三元组,其中 a+b+c \leq 49482,所以 49483 是正确的输出。
示例输入 3
1
示例输出 3
1
请注意,我们有 2^0 = 1.
示例输入 4
998984374864432412
示例输出 4
2003450165