ABC083 C - Multiple Gift (300点)

問題概要

問題のリンク

整数 $X$ と$Y$ が与えられる。

以下の条件を満たす数列Aを作る。

• $A$は$X$以上$Y$以下の整数からなる
• すべての$1 \leqq i \leqq |A|−1$に対し、$A_{i+1}$は $A_i$の倍数であり、かつ $A_{i+1}$ は $A_i$ より真に大きい

数列の長さが最大になるようにした時に、その最大値を求めなさい。

制約条件

• $1\leqq X \leqq Y \leqq 10^{18}$
• 入力は全て整数である

考えたこと

「$A_{i+1}$は $A_i$の倍数であり、かつ $A_{i+1}$ は $A_i$ より真に大きい」

という条件により $A_{i+1}$ は $A_i$ を正の整数倍(2以上)したものであることがわかる。よって配列に多くつめていくには、$A_i$の係数が小さければ小さいほどよい。2以上である必要があるので係数の最小値は2となる。
よって$Y$以上になるまで$X$に2をかけていく処理の回数を数えていけば答えが出る。

2の掛け算の繰り返しなので計算量は $O(\log n)$となる。よって制約条件$1\leqq X \leqq Y \leqq 10^{18}$は十分クリア。

あとは書くだけ。

コード

c.cs

using System;
using System.Linq;

class Program
{
    static void Main(string[] args) {
        long[] s = Console.ReadLine().Split().Select(long.Parse).ToArray();
        Console.WriteLine(solve(s[0], s[1]));
    }
    static int solve(long x, long y) {
        int count = 0;
        while(x <= y) {
            count ++;
            x *= 2;
        }
        return count;
    }
}