ARC088 C : Multiple Gift(300)
作成日：2017.12.31
最終更新日：2017.12.31
問題概要
$X$以上$Y$以下の整数からなる数列$\{A\}$で、$A_{i+1}$は$A_i$より大きい$A_i$の倍数であるものの要素数の最大値を求めよ。
制約
$1 \leq X \leq Y \leq 10^{18}$
考え方
条件より数列の初項は$X$以上であり、$A_{i+1} \geq 2A_i$が成り立つ。
各要素が$Y$以下であるという条件も踏まえると、$A_i$は取り得る最小のものを取るのが良い。
すなわち$A_i$$= 2^i X$$(i \geq 0)$とするのが最善である。
答えは$2^i X$$> Y$となる最小の$i$である。
ソースコード
マクロ等はこちら
LL X,Y;
int main(){
cin >> X >> Y;
int ans = 0;
while(X<=Y){
X <<= 1;
++ans;
}
cout << ans << endl;
return 0;
}解法まとめ
$2^i X$$> Y$となる最小の$i$が答えである。(5-10行)