/ WHOJ / 题库 /

培养细菌

培养细菌

题目描述

你是细菌的爱好者。你想在一个盒子里培养一些细菌。

最初,盒子是空的。每天早上,您可以将任意数量的细菌放入盒子中。而且到第二天早上,盒子里的每个细菌都会分裂成两个细菌。

您希望在某个早上准确地看到盒子中有 \(x\) 个细菌。(当然你也可以在最后的早上,放入一些细菌,使其正好等于 \(x\))

请你计算出最少需要放入的细菌数量。

格式

输入格式

只有一个正整数 \(x(1≤x≤10^9)\)。

输出格式

一个正整数表示最少需要放入的细菌数量。

样例1

输入样例1

5

输出样例1

2

样例解释

可以在第 \(1\) 天早上放入 \(1\) 个细菌,到第 \(3\) 天早上盒子中会有 \(4\) 个细菌,我们可以再添加 \(1\) 个细菌,使其正好为 \(5\) 个细菌。总共放入 \(2\) 个细菌。

限制

时间:\(1s\) 空间:\(64M\)

共有 \(10\) 个测试点:

第 \(1\) 个测试点:\(1≤x≤10\);

第 \(2\) 个测试点:\(1≤x≤10^2\);

第 \(3\) 个测试点:\(1≤x≤10^3\);

第 \(4\) 个测试点:\(1≤x≤10^4\);

第 \(5\) 个测试点:\(1≤x≤10^5\);

第 \(6\) 个测试点:\(1≤x≤10^6\);

第 \(7\) 个测试点:\(1≤x≤10^7\);

第 \(8\) 个测试点:\(1≤x≤10^8\);

第 \(9,10\) 个测试点:\(1≤x≤10^9\)。

来源

地址:\(zloj,J2021\)域
作者:\(jialiang2509\)
模拟赛\(T1\)