AtCoder ABC 083 C - Multiple Gift (5Q, 灰色, 300 点)

初歩的な Greedy の問題と言える。

• 問題へのリンク

問題概要

以上 以下の整数からなる数列 であって、

• 
• は で割り切れる

という条件を満たすものを考える。そのような数列の長さの最大値を求めよ。

制約

• 

考えたこと

基本的には、なるべく小さい値でスタートして、その次の値もなるべく小さくして、さらにその次の値もなるべく小さくして......というように考えれば良い。

そうすると、まず初項は

• 

とすればよい。二項目については、 よりも大きくて、 を割り切る最小の整数を持ってくればよい。それは、 である。よって、

• 

とすればよい。一般に、 が決まっているとき、

• 

とすればよい。こうして、 を超えるまで続けていけばよい。

毎回 2 倍になっていくことから、 ≒ 回程度で超えてしまうことがわかる。よって、愚直に 2 倍し続けても、計算時間には余裕がある。計算量をランダウの 記法で表すと、 とかける。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long X, Y;
    cin >> X >> Y;

    int res = 0;
    long long num = X;

    // 値が Y を超えるまで 2 倍し続ける
    while (num <= Y) {
        res++;  // カウントする
        num *= 2;
    }
    cout << res << endl;
}