yukicoder No.820 - Power of Two ★

$x$は$2^K$の倍数であるため、$x = c \times 2^K$と表せます。ということで、$1 \le x \le 2^N$という条件式は、$1 \le c \times 2^K \le 2^N$と変形できます。そして、$x$の個数は$c$の最大値に等しいです。したがって、$x$の個数は$\lfloor 2^N \div 2^K \rfloor$です。計算量は$O(N + K)$です。繰り返し二乗法を使うことで、計算量を$O(\log N + \log K)$まで減らすこともできます。

提出コード

#include <bits/stdc++.h>

using namespace std;

int main() {
  int N, K;
  cin >> N >> K;
  int ans = 1;
  for (int i = 0; i < N; i++) {
    ans *= 2;
  }
  for (int i = 0; i < K; i++) {
    ans /= 2;
  }
  cout << ans << endl;
  return 0;
}