← 返回题目列表

AtCoder · arc119_a

A. 119乘以2的23次方加1

中文机器翻译题面 查看原题

分数: 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