B - CTZ / AtCoder Beginner Contest 336
問題
正の整数 に対して、
を2進表記したときに末尾に連続する
の個数の最大値を
と表す。
ただし、
を2進表記したときに末尾が
であれば、
である。
正の整数 が与えられるとき、
を出力せよ。
入力
最初の1行に、整数 が与えられる。
条件
- 実行時間制限: 2s
- メモリ制限: 1024MB
出力
を1行で出力すること。
解法
ある整数を2進表記したときに、末尾に が
個並んでいるものとします。
（ただし、末尾から
個目の数字は
とします。）
このとき、この整数を とすると、
\begin{align}
x & = \cdots + 1 \cdot {2}^{k} + 0 \cdot {2}^{k - 1} + \cdots + 0 \cdot {2}^{1} + 0 \cdot {2}^{0} \\
& = \cdots + {2}^{k}
\end{align}
という形になるので、
は
の倍数であり、
の倍数ではないということが言えます。
従って、与えられた整数 に対して、割り切れる限り
で割ったときの、計算が行えた回数が答えとなります。
であり、この計算は
程度の計算量で行えるので、これは実行時間制限に間に合います。
ソースコード
main() 関数の中に、答えを出力する部分を直接実装しました。
int main() { // 値の入力 int n; cin >> n; int ans = 0; // 答えを表す整数 ans // n が 2 で割り切れる限り、以下の操作を続ける while (n % 2 == 0) { ans++; // 答えを1つ増やす n /= 2; // n を 2 で割った値にして更新する } cout << ans << endl; // 答えの出力 return 0; }
